Problem:
Counting Sort Counting sort can be used for sorting elements in an array which each of the n input elements is an integer in the range 0 to k. The idea of counting sort is to determine, for each input element x, the number of elements less than x as C[x]. This information can be used to place element x directly into its position in the output array B. This scheme must be modified to handle the situation in which several elements have the same value. Please see the following pseudocode for the detail: Counting-Sort(A, B, k)
1    for i = 0 to k
2        do C[i] = 0
3    for j = 1 to length[A]
4        do C[A[j]] = C[A[j]]+1
5    /* C[i] now contains the number of elements equal to i */
6    for i = 1 to k
7    do C[i] = C[i] + C[i-1]
8    /* C[i] now contains the number of elements less than or equal to i */
9    for j = length[A] downto 1
10       do B[C[A[j]]] = A[j]
11          C[A[j]] = C[A[j]]-1 Write a program which sorts elements of given array ascending order based on the counting sort. Input The first line of the input includes an integer n , the number of elements in the sequence. In the second line, n elements of the sequence are given separated by spaces characters. Output Print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character. Constraints  1 ≤ n ≤ 2,000,000  0 ≤ A[ i ] ≤ 10,000  Sample Input 1 7
2 5 1 3 2 3 0 Sample Output 1 0 1 2 2 3 3 5

Solution (Python):
def printAns( A ):
    n = len(A)
    for i in range(1, n-1):
        print( str( A[i] ), end=" ")
    print( str( A[n-1] ) )

def main():
    n = int( input() )
    A = [0]
    list = [int(x) for x in input().split()]
    A.extend(list)
    B = []
    C = []
    k = max(A)

    for i in range(k + 1):
        C.append(0)

    for i in range(n+1):
        B.append(0)

    for j in range(1, n+1):
        C[ A[j] ] += 1

    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]

    for j in reversed(range(n+1)):
        B[ C[ A[j] ] ] = A[j]
        C[ A[j] ] -= 1

    printAns(B)

if __name__ == "__main__":
    main()

Solution (Python):
def printAns( A ):
    n = len(A)
    for i in range(1, n-1):
        print( str( A[i] ), end=" ")
    print( str( A[n-1] ) )

def main():
    n = int( input() )
    A = [0]
    list = [int(x) for x in input().split()]
    A.extend(list)
    B = []
    C = []
    k = max(A)

    for i in range(k + 1):
        C.append(0)

    for i in range(n+1):
        B.append(0)

    for j in range(1, n+1):
        C[ A[j] ] += 1

    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]

    for j in reversed(range(n+1)):
        B[ C[ A[j] ] ] = A[j]
        C[ A[j] ] -= 1

    printAns(B)

if __name__ == "__main__":
    main()

Solution (Python):
def printAns( A ):
    n = len(A)
    for i in range(1, n-1):
        print( str( A[i] ), end=" ")
    print( str( A[n-1] ) )

def main():
    n = int( input() )
    A = [0]
    list = [int(x) for x in input().split()]
    A.extend(list)
    B = []
    C = []
    k = max(A)

    for i in range(k + 1):
        C.append(0)

    for i in range(n+1):
        B.append(0)

    for j in range(1, n+1):
        C[ A[j] ] += 1

    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]

    for j in reversed(range(n+1)):
        B[ C[ A[j] ] ] = A[j]
        C[ A[j] ] -= 1

    printAns(B)

if __name__ == "__main__":
    main()

Solution (Python):
def printAns( A ):
    n = len(A)
    for i in range(1, n-1):
        print( str( A[i] ), end=" ")
    print( str( A[n-1] ) )

def main():
    n = int( input() )
    A = [0]
    list = [int(x) for x in input().split()]
    A.extend(list)
    B = []
    C = []
    k = max(A)

    for i in range(k + 1):
        C.append(0)

    for i in range(n+1):
        B.append(0)

    for j in range(1, n+1):
        C[ A[j] ] += 1

    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]

    for j in reversed(range(n+1)):
        B[ C[ A[j] ] ] = A[j]
        C[ A[j] ] -= 1

    printAns(B)

if __name__ == "__main__":
    main()

Solution (Python):
flg = 0
n = int(input())
l = list(map(int,input().split()))
bucket = [0]*10000
for i in range(n):
    bucket[l[i]] += 1
    if flg < l[i]:
        flg = l[i]
for i in range(flg):
    for j in range(bucket[i]):
        print(i,end = ' ')
for i in range(bucket[flg]-1):
    print(flg,end=' ')
print(flg)

Solution (Python):
def countingSort(A, B, k):
    C = [0 for i in range(k+1)]

    for i in A:
        C[i] += 1

    for i in range(1, k+1):
        C[i] += C[i-1]

    for i in A[::-1]:
        B[C[i]-1] = i
        C[i] -= 1

    return B


n = int(input())
A = list(map(int, input().split()))
k = max(A)
B = [0 for x in range(n)]
B = countingSort(A, B, k)
print(*B)

Solution (Python):
def counting_sort(a, b, k):
	c = [0] * (k + 1)
	for i in range(len(a)):
		c[a[i]] += 1

	for i in range(1, k+1):
		c[i] = c[i] + c[i - 1]

	for i in range(len(a) - 1, -1, -1):
		num = a[i]
		b[c[num] - 1] = num
		c[num] -= 1

n = int(input())
a = list(map(int, input().split()))
b = [0] * n
k = max(a)
counting_sort(a, b, k)
print(b[0], end='')
for i in range(1, n):
	print(' ' +  str(b[i]), end='')
print()

Solution (Python):
def counting_sort(a, b, k):
	c = [0] * (k + 1)
	for i in range(len(a)):
		c[a[i]] += 1

	for i in range(1, k+1):
		c[i] = c[i] + c[i - 1]

	for i in range(len(a) - 1, -1, -1):
		c[a[i]] -= 1
		b[c[a[i]]] = a[i]

n = int(input())
a = list(map(int, input().split()))
b = [0] * n
counting_sort(a, b, max(a))
print(b[0], end='')
for i in range(1, n):
	print(' ' +  str(b[i]), end='')
print()

Solution (Python):
def counting_sort(a, b, k):
	c = [0] * (k + 1)
	for i in range(len(a)):
		c[a[i]] += 1

	for i in range(1, k+1):
		c[i] = c[i] + c[i - 1]

	for i in range(len(a) - 1, -1, -1):
		c[a[i]] -= 1
		b[c[a[i]]] = a[i]

n = int(input())
a = list(map(int, input().split()))
b = [0] * n
counting_sort(a, b, max(a))
print(b[0], end='')
for i in range(1, n):
	print(' ' +  str(b[i]), end='')
print()

Solution (Python):

def counting_sort(a, b, k):
	c = [0] * (k + 1)
	for i in range(len(a)):
		c[a[i]] += 1
	for i in range(1, k + 1):
		c[i] += c[i - 1]
	for i in range(len(a) - 1, -1, -1):
		c[a[i]] -= 1
		b[c[a[i]]] = a[i]
		
n = int(input())
a = list(map(int, input().split()))
b = [0] * n
counting_sort(a, b, max(a))
print(b[0], end='')
for i in range(1, n):
	print(' ' + str(b[i]), end='')
print()

Solution (Python):
def CountingSort(A, k):
    B = [0]*(len(A)+1)
    C = [0]*(k+1)
    for i in A:C[i]+=1
    for i in range(1,k+1):C[i]=C[i]+C[i-1]
    for i in range(n-1,-1,-1):
        B[C[A[i]]]=A[i]
        C[A[i]]-=1
    return B[1:]
n = int(input())
A = [int(i) for i in input().split()]
B = CountingSort(A,10000)
ans = ""
for i in B:ans+=str(i)+" "
print(ans[:-1])

Solution (Python):
def counting_sort(MAX):
    C = [0 for _ in range(MAX+1)]

    for i in range(N):
        C[A[i]] += 1

    for i in range(1, MAX+1):
        C[i] = C[i] + C[i-1]

    for i in range(N-1, -1, -1):
        C[A[i]] -= 1
        B[C[A[i]]] = A[i]

N = int(input())
A = list(map(int, input().split()))

MAX = 0
for n in A:
    if MAX < n:
        MAX = n

B = [0 for _ in range(N)]
counting_sort(MAX)
print(" ".join(map(str, B)))

Solution (Python):
def counting_sort(MAX):
    C = [0 for _ in range(MAX+1)]

    for i in range(N):
        C[A[i]] += 1

    for i in range(1, MAX+1):
        C[i] = C[i] + C[i-1]

    for i in range(N-1, -1, -1):
        C[A[i]] -= 1
        B[C[A[i]]] = A[i]

N = int(input())
A = list(map(int, input().split()))

MAX = 0
for n in A:
    if MAX < n:
        MAX = n

B = [0 for _ in range(N)]
counting_sort(MAX)
print(" ".join(map(str, B)))

Solution (Python):
def counting_sort(MAX):
    C = [0 for _ in range(MAX+1)]

    for i in range(N):
        C[A[i]] += 1

    for i in range(1, MAX+1):
        C[i] = C[i] + C[i-1]

    for i in range(N-1, -1, -1):
        C[A[i]] -= 1
        B[C[A[i]]] = A[i]

N = int(input())
A = list(map(int, input().split()))

MAX = 10001

B = [0 for _ in range(N)]
counting_sort(MAX)
print(" ".join(map(str, B)))

Solution (Python):
def counting_sort(A, k):
    B = [0] * len(A)
    C = [0] * k

    for a in A:
        C[a] += 1

    for i in range(1, k):
        C[i] += C[i - 1]

    for a in reversed(A):
        B[C[a] - 1] = a
        C[a] -= 1

    return B


def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    print(*counting_sort(A, 10001))


main()

Solution (Python):
def counting_sort(A, k):
    B = [0] * len(A)
    C = [0] * k

    for a in A:
        C[a] += 1

    for i in range(1, k):
        C[i] += C[i - 1]

    for a in A:
        B[C[a] - 1] = a
        C[a] -= 1

    return B


def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    print(*counting_sort(A, 10001))


main()

Solution (Python):
def counting_sort(A, n, k):
    C = [0] * (k + 1)
    B = [0] * n
    for ai in A:
        C[ai] += 1
    
    for i in range(1, k + 1):
        C[i] += C[i - 1]
    for ai in reversed(A):
        B[C[ai] - 1] = ai
        C[ai] -= 1
    return B
n = int(input())
k = 10000
print(*counting_sort(list(map(int, input().split())), n, k))

Solution (Python):
n = int(input())
A = [int(_) for _ in input().split()]
len_C = max(A) + 1
C = [0] * (len_C)
B = [0] * n

for i in range(n):
    C[A[i]] += 1

for i in range(1, len_C):
    C[i] += C[i-1]


for i in range(n-1, -1, -1):
    
    B[C[A[i]]-1] = A[i]
    C[A[i]] -= 1

for i in range(n-1):
    print(B[i], end=' ')
print(B[n-1])

Solution (Python):
n=int(input())
A=[0]*(n+1)
B=[0]*(n+1)
i=0
mx=(1<<30)*-1
for v in list(map(int,input().split())):
	A[i+1] = v
	mx=max(mx,A[i+1])
	i+=1	

C=[0]*(mx+1)
for i in range(n):
	C[A[i+1]]+=1
for i in range(1,mx+1):
	C[i] += C[i-1]
for i in range(n,0,-1):
	B[C[A[i]]] = A[i]
	C[A[i]]-=1

st=str(B[1])
for i in range(2,n+1):
	st += ' ' + str(B[i])
print(st)

Solution (Python):
def counting_sort(array, max_val = 10000):
    max_val = min(max(array), max_val)
    counting_array = [0 for x in range(0, max_val+1)]
    sorted_array = [0 for x in range(len(array))]

    for i in array:
        counting_array[i] += 1

    for i in range(1, max_val + 1):
        counting_array[i] += counting_array[i-1]

    for i in range(len(array))[::-1]:
        val = array[i]
        sorted_array[counting_array[val]-1] = val
        counting_array[val] -= 1

    return sorted_array


def main():
    n = int(input())
    array = [int(x) for x in input().split()]
    sorted_array = counting_sort(array)
    print(" ".join(map(str, sorted_array)))
    return

main()

Solution (Python):
def counting_sort(array, max_val=10000):
    max_val = min(max(array), max_val)
    counting_array = [0] * (max_val+1)
    sorted_array = [0 for x in range(len(array))]

    for i in array:
        counting_array[i] += 1

    for i in range(1, max_val + 1):
        counting_array[i] += counting_array[i-1]

    for i in range(len(array))[::-1]:
        val = array[i]
        sorted_array[counting_array[val]-1] = val
        counting_array[val] -= 1

    return sorted_array


def main():
    n = int(input())
    array = [int(x) for x in input().split()]
    sorted_array = counting_sort(array)
    print(" ".join(map(str, sorted_array)))
    return

main()

Solution (Python):
def CountingSort(A, k):
    C = [0] * (k+1)
    n = len(A)
    
    for a in A:
        C[a] = C[a] + 1


    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]

    B = [0] * n
    for j in range(n-1, -1, -1):
        rank = C[ A[j] ]
        B[ rank  - 1] = A[j]
        C[ A[j] ] = C[ A[j] ] - 1

    return B

n = int(input())
A = [int(i) for i in input().split()]

ans = CountingSort(A, 10000)
print(' '.join([str(i) for i in ans]))

Solution (Python):
def CountingSort(A, k):
    C = [0] * (k+1)
    n = len(A)
    
    for a in A:
        C[a] = C[a] + 1


    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]

    B = [0] * n
    for a in A:
        rank = C[a]
        B[rank  - 1] = a
        C[a] = C[a] - 1

    return B

n = int(input())
A = [int(i) for i in input().split()]

ans = CountingSort(A, 10000)
print(' '.join([str(i) for i in ans]))

Solution (Python):
def CountingSort(A, B, k):
    C = [0] * (k+1)
    for i in range(k):
        C[i] = 0
    
    for j in range(0,n):
        C[A[j]]+=1
    
    
    for i in range(1,k+1):
        C[i] = C[i] + C[i-1]
    
    for j in range(n-1,-1,-1):
        B[C[A[j]]] = A[j]
        C[A[j]]-=1
        

n = int(input())
A = list(map(int,input().split()))
B = [0] * (n+1)
CountingSort(A,B,100000)
print(' '.join(map(str,B[1:])))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = [0] * (n+1)
m = max(a)
c = [0] * (m+1)
for i in a:
    c[i] += 1
for j in range(1, m+1):
    c[j] = c[j] + c[j-1]

for k in reversed(a):
    
    
    b[c[k]] = k
    c[k] -= 1

for i in range(1,n):
    print(b[i], end=' ')
print(b[n])

Solution (Python):
def InputData():
    
    sequence_len = int(input())
    sequence = [None] + [int(a) for a in input().split(" ")]

    return sequence_len, sequence

def countingSort(sequence, k, sequence_len):
    
    B = [None]*(sequence_len+1)
    C = [0]*k
    
    for j in range(1, sequence_len+1):
        C[sequence[j]] += 1
    
    for i in range(1, k):
        C[i] = C[i] + C[i-1]
    
    for j in range(sequence_len, 0, -1):
        B[C[sequence[j]]] = sequence[j]
        C[sequence[j]] -= 1

    return B

def PrintOut(sequence):
    print(' '.join( map(str, sequence)))

def main():
    [sequence_len, sequence] = InputData()
    sequence_out = countingSort(sequence, 10000, sequence_len)
    PrintOut(sequence_out[1:])

if __name__=="__main__":
    main()

Solution (Python):
def counting_sort(lst,ans,max):
    cnt_lst = [0] * (max+1)
    for i in range(0,len(lst)):
        cnt_lst[lst[i]] += 1
    for j in range(1,max+1):
        cnt_lst[j] = cnt_lst[j] + cnt_lst[j-1]

    for k in range(len(lst)-1,-1,-1):
        ans[cnt_lst[lst[k]]-1] = lst[k]
        cnt_lst[lst[k]] -= 1
    return ans

n = int(input())
n_lst = list(map(int,input().split()))
ans = [0] * len(n_lst)
ans = map(str,counting_sort(n_lst,ans,max(n_lst)))
print(' '.join(ans))

Solution (Python):
def countingsort(a,k):
    c=[0]*(k+1)
    n=len(a)
    for i in a:
        c[i]+=1
    for i in range(1,k+1):
        c[i]=c[i]+c[i-1]
    b=[0]*n
    for i in range(n-1,-1,-1):
        b[c[a[i]]-1]=a[i]
        c[a[i]]-=1
    return b
o=int(input())
a=list(map(int,input().split()))
q=max(a)
ret=countingsort(a,q)
for i in range(o):
    if i!=o-1:
        print(ret[i],end=" ")
    else:
        print(ret[i])

Solution (Python):

n = int(input())
a = list(map(int, input().split()))

def countSort(a):
    N = max(a)
    c = [0]*(N+2)
    b = [0]*len(a)
    for i in a:
        c[i] += 1
    for i in range(1,len(c)):
        c[i] += c[i-1]
        
    for i in a:
        b[c[i]-1] = i
        c[i] -= 1
    print(*b)

countSort(a)

Solution (Python):
def counting_sort(A):
    
    bucket = {}
    for i in range(10000):
        bucket[i] = 0

    for a in A:
        bucket[a] += 1



    k = 0
    for i in range(10000):
        for j in range(bucket[i]):
            A[k] = i
            k += 1

n = int(input())
A = list(map(int, input().split()))

counting_sort(A)

print(*A)

Solution (Python):
def counting_sort(A):
    
    bucket = []
    for i in range(10000):
        bucket.append(0)

    for a in A:
        bucket[a] += 1

    k = 0
    for i in range(10000):
        for j in range(bucket[i]):
            A[k] = i
            k += 1

n = int(input())
A = list(map(int, input().split()))

counting_sort(A)

print(*A)

Solution (Python):
def counting_sort(A, B, k):
    n = len(A)
    B = [0] * n

    C = [0] * (k+1)

    
    for a in A:
        
        C[a] += 1
    
    

    
    for i in range(1, k+1):
        C[i] += C[i-1]

    

    
    for i in range(n-1, -1, -1):
        index_to_insert = C[A[i]] - 1
        C[A[i]] -= 1
        B[index_to_insert] = A[i]
        

    return B

_ = int(input())
A = list(map(int, input().split()))

B = []
B = counting_sort(A, B, 10000)
print(*B)

Solution (Python):
def CountingSort(A,B,num):

	k = max(A)
	C = [0 for _ in range(k+1)]
	
	for i in A:
		C[i] += 1

	
	for j in range(1,k+1):
		C[j] += C[j-1]
	for h in range(num-1,-1,-1):
		B[C[A[h]]-1] = A[h]
		C[A[h]] -= 1

if __name__ == '__main__':

	num = int(input())
	A = [int(i) for i in input().split()]

	B = [0 for _ in range(num+1)]
	CountingSort(A,B,num)

	B.pop()
	print(" ".join(map(str,B)))

Solution (Python):
input()
print " ".join(sorted(raw_input().split(),key=int))

Solution (Python):
def counting_sort(a, b, k):
    c = [0 for _ in range(k + 1)]
    for i in range(len(a)):
        c[a[i]] += 1
    for i in range(1, len(c)):
        c[i] += c[i -1]
    for i in range(len(a) - 1, -1, -1):
        b[c[a[i]] - 1] = a[i]
        c[a[i]] -= 1

n = input()
a = list(map(int, input().split()))
b = [0 for _ in range(len(a))]
counting_sort(a, b, max(a))
print(*b)

Solution (Python):
def countingsort(a, b, k):
    c = [0 for i in range(k + 1)]
    for i in range(len(a)):
        c[a[i]] += 1
    for i in range(1, len(c)):
        c[i] += c[i - 1]
    for i in range(len(a) - 1, -1, -1):
        b[c[a[i]] - 1] = a[i]
        c[a[i]] -= 1

n = int(input())
a = list(map(int, input().split()))
b = [0] * n
countingsort(a, b, max(a))
print(*b)

Solution (Python):

def CountingSort(A, k):
    count = [0] * k
    offset = [0] * k
    for x in A:
        count[x] += 1
    offset[0] = 0
    for i in xrange(1, k):
        offset[i] = offset[i-1] + count[i-1]

    R = [0] * len(A)
    for i in xrange(len(A)):
        target = A[i]
        R[offset[target]] = target
        offset[target] += 1
    return R

n = int(raw_input())
A = map(int, raw_input().split())
B = CountingSort(A, 10000)
print ' '.join(map(str, B))

Solution (Python):
def CountingSort(A,B,k):
    C = []
    for i in range(0,k+1):
        C.append(0)
    for j in A:
        C[j] += 1
    for i in range(0,k+1):
        while(C[i] != 0):
            B.append(i)
            C[i] -= 1
B = []
n = int(input())
st = input()
A = list(map(int,st.split()))
max = 0
for x in A:
    if x > max:
        max = x
CountingSort(A,B,max)
for i in range(0,n-1):
    print(B[i],end=" ")
print(B[n-1])

Solution (Python):




import array
import sys


def counting_sort(a, n, k=10000):
    b = array.array("I", (0 for x in range(n)))
    c = array.array("I", (0 for x in range(k + 1)))
    for j in range(0, n):
        c[a[j]] += 1
    for i in range(0, k + 1):
        c[i] += c[i - 1]
    for j in range(n - 1, -1, -1):
        b[c[a[j]] - 1] = a[j]
        c[a[j]] -= 1
    return b


def main():
    n = int(sys.stdin.readline())
    a = array.array("I", map(int, sys.stdin.readline().split()))
    print(" ".join(map(str, counting_sort(a, n))))


if __name__ == "__main__":
    main()

Solution (Python):
n = int(raw_input())
S = map(int,raw_input().strip().split(' '))

def counting_sort(S,k):
    C = [0]*(k+1)
    B = [0]*len(S)
    for v in S:
        C[v] += 1
    for i in range(1,k+1):
        C[i] += C[i-1]
    for i in range(len(S)):
        B[C[S[i]]-1] = S[i]
        C[S[i]] -= 1
    return B

B = counting_sort(S,10000)
for b in B:
    print b,

Solution (Python):


def counting_sort(array):
    cnt = [0 for i in range(max(array)+1)]
    result = [0 for  i in range(len(array))]

    for j in range(len(array)):
        cnt[array[j]] += 1

    for i in range(1, max(array)+1):
        cnt[i] += cnt[i-1]

    for j in reversed(range(len(array))):
        result[cnt[array[j]]-1] = array[j]
        cnt[array[j]] -= 1

    return result

n = int(input())
numbers = list(map(int, input().split()))
print(' '.join(map(str, counting_sort(numbers))))

Solution (Python):
n, a = int(input()), list(map(int, input().split()))
b, c = [0] * n, [0] * 10001

for j in range(n):
    c[a[j]] += 1

prev = -1
for i in range(10001):
    c[i] = prev = c[i] + prev

for j in range(n - 1, -1, -1):
    aj = a[j]
    b[c[aj]] = aj
    c[aj] -= 1

print(*b)

Solution (Python):
"""Counting Sort."""

def countingSort(A, B, k):
    """Sort the elements of list A with Counting Sort algorithm.

    n is the length of A.
    The elements of A are intergers between 0 and k, inclusive.
    B is the output list where the sorted elements will be arranged.
    
    Print the elements of B in a line separated by a space character.
    """

    C = [0 for i in range(k + 1)]

    for i in A:
        C[i] += 1

    for i in range(1, k + 1):
        C[i] = C[i] + C[i - 1]
    
    for i in A[::-1]:
        B[C[i]] = i
        C[i] -= 1

    print(*B[1:])


n = int(input())

A = list(map(int, input().split()))

B = [0 for i in range(n + 1)]

k = max(A)

countingSort(A, B, k)

Solution (Python):
"""Counting Sort."""

def countingSort(A, B):
    """Sort the elements of list A with Counting Sort algorithm.

    n is the length of A.
    The elements of A are intergers between 0 and k, inclusive.
    B is the output list where the sorted elements will be arranged.
    
    Print the elements of B in a line separated by a space character.
    """

    C = [0 for i in range(10001)]

    for i in A:
        C[i] += 1

    for i in range(1, 10001):
        C[i] = C[i] + C[i - 1]
    
    for i in A[::-1]:
        B[C[i]] = i
        C[i] -= 1

    print(*B[1:])


n = int(input())

A = list(map(int, input().split()))

B = [0 for i in range(n + 1)]



countingSort(A, B)

Solution (Python):
"""Counting Sort."""

def countingSort(A, n):
    """Sort the elements of list A with Counting Sort algorithm.

    n is the length of A.
    The elements of A are intergers between 0 and k, inclusive.
    B is the output list where the sorted elements will be arranged.
    
    Print the elements of B in a line separated by a space character.
    """

    k = max(A)
    
    C = [0 for i in range(k + 1)]

    for i in A:
        C[i] += 1

    for i in range(1, k + 1):
        C[i] = C[i] + C[i - 1]

    B = [0 for i in range(n + 1)]
    
    for i in A[::-1]:
        B[C[i]] = i
        C[i] -= 1

    print(*B[1:])


n = int(input())

A = list(map(int, input().split()))

countingSort(A, n)

Solution (Python):
"""Counting Sort."""

def countingSort(A, n):
    """Sort the elements of list A with Counting Sort algorithm.

    n is the length of A.
    The elements of A are intergers between 0 and 10000, inclusive.
    B is the output list where the sorted elements will be arranged.
    
    Print the elements of B in a line separated by a space character.
    """

    C = [0 for i in range(10001)]

    for i in A:
        C[i] += 1

    for i in range(1, 10001):
        C[i] = C[i] + C[i - 1]

    B = [0 for i in range(n + 1)]
    
    for i in A[::-1]:
        B[C[i]] = i
        C[i] -= 1

    print(*B[1:])


n = int(input())

A = list(map(int, input().split()))

countingSort(A, n)

Solution (Python):
"""Counting Sort."""

def countingSort(A, n):
    """Sort the elements of list A with Counting Sort algorithm.

    n is the length of A.
    The elements of A are intergers between 0 and 10000, inclusive.
    B is the output list where the sorted elements will be arranged.
    
    Print the elements of B in a line separated by a space character.
    """

    C = [0 for i in range(10001)]

    for i in A:
        C[i] += 1

    for i in range(1, 10001):
        C[i] = C[i] + C[i - 1]

    B = [0 for i in range(n + 1)]
    
    for i in A[::-1]:
        B[C[i]] = i
        C[i] -= 1

    print(*B[1:])


import sys

n = int(sys.stdin.readline())

A = list(map(int, sys.stdin.readline().split()))

countingSort(A, n)

Solution (Python):
"""Counting Sort."""

def countingSort(A, n):
    """Sort the elements of list A with Counting Sort algorithm.

    n is the length of A.
    The elements of A are intergers between 0 and 10000, inclusive.
    B is the output list where the sorted elements will be arranged.
    
    Print the elements of B in a line separated by a space character.
    """

    C = [0 for i in range(10001)]

    for i in A:
        C[i] += 1

    for i in range(1, 10001):
        C[i] += C[i - 1]

    B = [0 for i in range(n + 1)]
    
    for i in A[::-1]:
        B[C[i]] = i
        C[i] -= 1

    print(*B[1:])


import sys

n = int(sys.stdin.readline())

A = list(map(int, sys.stdin.readline().split()))

countingSort(A, n)

Solution (Python):
"""Counting Sort."""

def countingSort(A, n):
    """Sort the elements of list A with Counting Sort algorithm.

    n is the length of A.
    The elements of A are intergers between 0 and 10000, inclusive.
    B is the output list where the sorted elements will be arranged.
    
    Print the elements of B in a line separated by a space character.
    """

    C = [0 for i in range(10001)]

    for i in A:
        C[i] += 1

    for i in range(1, 10001):
        C[i] += C[i - 1]

    B = [0 for i in range(n + 1)]
    
    for i in reversed(A):
        B[C[i]] = i
        C[i] -= 1

    print(*B[1:])


import sys

n = int(sys.stdin.readline())

A = list(map(int, sys.stdin.readline().split()))

countingSort(A, n)

Solution (Python):
n = int(raw_input())
A = map(int, raw_input().split())
B = [0] * n

def CountingSort(A, B, k):
    C = [0] * (k+1)
    for j in xrange(n):
        C[A[j]] += 1
    for i in xrange(1,k+1):
        C[i] = C[i] + C[i-1]
    for j in xrange(n-1,-1,-1):
        B[C[A[j]]-1] = A[j]
        C[A[j]] -= 1
    return 0

def main():
    CountingSort(A, B, 10000)
    print ' '.join(map(str,B))
    return 0

main()

Solution (Python):
class CountingSort:
    def countingSort(self, a, b, k):
        n = len(a)
        c = [0] * (k + 1)
        for j in a:
            c[j] += 1
        
        for i in range(1, k + 1):
            c[i] = c[i] + c[i-1]
            
        for j in a[::-1]:
            b[c[j]] = j
            c[j] -= 1
        return b[1:]

if __name__ == '__main__':
    n = int(input().rstrip())
    a = [int(i) for i in input().rstrip().split(" ")]
    b = [0] * (n + 1)
    k = max(a)
    x = CountingSort()
    print(" ".join([str(i) for i in x.countingSort(a, b, k)]))

Solution (Python):
def counting_sort(A, k):
    B, C = [], [0]*(k+1)
    for j in range(0, len(A)):
        C[A[j]] += 1
    for i in range(0, len(C)):
        while True:
            if C[i] != 0:
                B.append(i)
                C[i] -= 1
            else:
                break
    return B

input()
num = list(map(int, input().split()))
result = counting_sort(num, max(num))
print(*result)

Solution (Python):
def countingsort(A,B,k):
    global n
    C=[0 for i in xrange(k+1)]
    for j in xrange(1,n+1):
        C[A[j]]+=1
    for i in xrange(1,k+1):
        C[i]+=C[i-1]
    for j in xrange(n,0,-1):
        B[C[A[j]]]=A[j]
        C[A[j]]-=1

n=input()
A=[0]
a=map(int,raw_input().split())
for i in a:
    A.append(i)
B=[0]*n+[0]
k=max(A)
countingsort(A,B,k)
B=map(str,B)
print(" ".join(B[1:]))

Solution (Python):
import sys

def countingSort(A, B, k):
    C = [0] * (k + 1)

    for j in range(0, len(A)):
        C[A[j]] += 1

    for i in range(1, k + 1):
        C[i] += C[i - 1]

    B = [0] * (max(C) + 1)
    for j in range(len(A) - 1, -1, -1):
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1

    del B[0]
    print " ".join([str(b) for b in B])

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    B = []
    countingSort(A, B, max(A))

Solution (Python):


def counting_sort(A, k):
    n = len(A)
    B = ['0' for i in range(n + 1)]
    C = [0 for i in range(0, k + 1)]

    
    for j in range(0, n):
        C[A[j]] += 1

    
    for i in range(0, k):
        C[i + 1] +=  C[i]

    for j in reversed(range(0, n)):
        B[C[A[j]]] = str(A[j])
        C[A[j]] -= 1
    return ' '.join(B[1:])

n = int(input())
A = list(map(int, input().split()))
k = max(A)
print(counting_sort(A, k))

Solution (Python):
import sys

'''
def countingSort(A, B, k):
    C = [0] * (k + 1)

    for j in range(len(A)):
        C[A[j]] += 1

    for i in range(1, k + 1):
        C[i] += C[i - 1]

    B = [0] * (max(C) + 1)
    for j in range(len(A) - 1, -1, -1):
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1

    del B[0]
    print " ".join([str(b) for b in B])
    '''

def countingSort(A, B, k):
    C = [0] * (k + 1)
    for i in range(len(A)):
        C[A[i]] += 1
    for i in range(len(C)):
        for j in range(C[i]):
            B.append(i)
    print " ".join([str(b) for b in B])

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    B = []
    countingSort(A, B, 10000)

Solution (Python):
import sys

def countingSort(A, k):
    Sorted = []
    Cnt = [0] * (k + 1)

    for i in range(len(A)):
        Cnt[A[i]] += 1

    for i in range(len(Cnt)):
        for j in range(Cnt[i]):
            Sorted.append(i)

    print " ".join([str(v) for v in Sorted])

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    countingSort(A, 10000)

Solution (Python):


def countSort(A, m):
    count = [0]*(m+1)
    n = len(A)
    B = [0]*2000001
    j = 0
    for i in range(n):
        count[A[i]] += 1
    for i in range(1, m):
        count[i] += count[i-1]
    for i in range(n-1, -1, -1):
        j = count[A[i]]
        B[j] = A[i]
        count[A[i]] = j-1
    for i in range(n):
        A[i] = B[i+1]
    return A

n = int(raw_input())
A = map(int, raw_input().split())
B = countSort(A, 10000)
print " ".join(map(str, B))

Solution (Python):
def countingSort(A,k):
    C = {}
    for ai in A:
        C[ai] = C.get(ai,0) + 1
    for i in range(1,k+1):
        C[i] = C.get(i,0) + C.get(i-1,0)
    B = A[:]
    for ai in A:
        B[C[ai]-1] = ai
        C[ai] -= 1
    return B

if __name__=='__main__':
    n=int(input())
    print(*countingSort(list(map(int,input().split())),10000))

Solution (Python):
def countingSort(A,k):
    C = {}
    for ai in A:
        C[ai] = C.get(ai,0) + 1
    for i in range(1,k+1):
        C[i] = C.get(i,0) + C.get(i-1,0)
    B = A[:]
    for ai in A[::-1]:
        B[C[ai]-1] = ai
        C[ai] -= 1
    return B

if __name__=='__main__':
    n=int(input())
    print(*countingSort(list(map(int,input().split())),10000))

Solution (Python):
def countingsort(a, n):
    c = [0]*10001

    for i in range(n):
        c[a[i]] += 1

    for j in range(1, 10001):
        c[j] += c[j - 1]

    b = [0]*(n+1)

    for k in range(n, 0, -1):
        b[c[a[k-1]]] = a[k-1]
        c[a[k-1]] -= 1

    return b[1:]


n = int(input())
a = list(map(int, input().split()))
print(*countingsort(a, n))

Solution (Python):
def counting_sort(a,k):
    C = []
    for i in range(k):
        C.append(0)
    for ai in a:
        C[ai] += 1
    s = 0
    for i in range(k):
        s += C[i]
        C[i] = s
    b = []
    for i in range(len(a)):
        b.append(None)
    p = 0
    for i in range(k):
        while p < C[i]:
            b[p] = i
            p += 1
    return b


n = int(raw_input())
a = map(int,raw_input().split(' '))
print ' '.join(map(str,counting_sort(a,10000)))

Solution (Python):
class CountingSort:
    def countingSort(self, a, b, k):
        n = len(a)
        c = [0] * (k + 1)
        for j in a:
            c[j] += 1
         
        for i in range(1, k + 1):
            c[i] = c[i] + c[i-1]
             
        for j in a[::-1]:
            b[c[j]] = j
            c[j] -= 1
        return b[1:]
 
if __name__ == '__main__':
    n = int(input().rstrip())
    a = [int(i) for i in input().rstrip().split(" ")]
    b = [0] * (n + 1)
    k = max(a)
    x = CountingSort()
    print(" ".join([str(i) for i in x.countingSort(a, b, k)]))