Count Sort:

Count Sort basically tells you how many numbers are present before and after the current number observing which, you can sort the numbers. Lets say A = [5,1,4,3,2] . Here the count for 3 would be 3 as it is the 3rd element in the sorted list.

It works as follows:

• Create an array say OUTPUT of having the same length as the input array.
• Create another array say COUNT of length depending on the constraint and fill them with '0's
• Then run through the input array and keep on increasing the count in the COUNT array.
• Once this is done, your COUNT array will consists of number of occurrences of each input character.
• Now in the COUNT array, start with the second element and add it to the previous element.Keep on repeating this until we get to the end of the array (A little like Fibonacci Series)
• Now is the time to add numbers in the sorted order. Start iterating on the input array.
• Consider element 2 of input array, its value in the COUNT array will be 2 meaning it will be the 2nd element in the sorted array. So place 2 at position '1' in the OUTPUT array.

def CountSort(arr):
    output = [0 for i in range(len(arr))]

    count = [0 for i in range(100)]

    for i in range(len(arr)):
        count[arr[i]]+=1

    for i in range(1,100):
        count[i]+=count[i-1]
    for i in range(len(arr)):
        output[count[arr[i]]-1] = arr[i]
        count[arr[i]]-=1

    for i in output:
        print i,


n=int(raw_input())
arr = map(int,raw_input().split())
CountSort(arr)