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):
import array
import sys
def counting_sort(A, B, n, k=10000):
    C = array.array('I', [0 for i in range(k+1)])
    for j in range(0, n):
        x = A[j]
        C[x] += 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

n = int(input())
A = list(map(int , sys.stdin.readline()[:-1].split()))

B = array.array("I", [0 for i in range(n)])
counting_sort(A, B, n)

print(*B)

Solution (Python):


def Max(A):
    max=0
    for i in range(len(A)):
        if A[i]>max:
            max=A[i]
    return max

def CS(A,n):
    B=[]
    C=[]
    cn=Max(A)+1
    for i in range(n):
        B.append(0)
    for i in range(cn):
        C.append(0)
    for j in range(n):
        C[A[j]]+=1
    for i in range(1,cn):
        C[i]+=C[i-1]
    for j in reversed(range(n)):
        B[C[A[j]]-1]=A[j]
        C[A[j]]-=1
    for i in range(len(B)):
        B[i]=str(B[i])
    print(" ".join(B))
 
    
if __name__=="__main__":
    n=int(input())
    A=input().split(" ")
    for i in range(n):
        A[i]=int(A[i])
    CS(A,n)

Solution (Python):



def counting_sort(target_list):
    counter = [0 for i in range(10000)]

    for n in target_list:
        counter[n] += 1

    for i in range(1,10000):
        counter[i] = counter[i] + counter[i-1]

    result = [0 for i in range(len(target_list))]
    for n in target_list[::-1]:
        result[counter[n] - 1] = n
        counter[n] -= 1
    
    return result
if __name__ == "__main__":
    n_list = int(input())
    target_list = [int(s) for s in input().split()]
    sorted_list = counting_sort(target_list)
    print(" ".join([str(s) for s in sorted_list]))

Solution (Python):




import sys


def counting_sort(A, max_occurance):
    result = [0] * array_length
    count_list = [0] * max_occurance

    for j in range(array_length):
        count_list[A[j]] += 1
    

    for i in range(1, max_occurance):
        count_list[i] += count_list[i - 1]
    

    for m in array[::-1]:
        result[count_list[m] - 1] = m
        count_list[m] -= 1

    return result


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    assert len(array) == array_length
    max_elem = int(1e4)
    result = counting_sort(A=array, max_occurance=max_elem)
    print(*result)

Solution (Python):




import sys


def counting_sort(A, max_occurance):
    result = [0] * array_length
    count_list = [0] * max_occurance

    for j in range(array_length):
        count_list[A[j]] += 1
    

    for i in range(1, max_occurance):
        count_list[i] += count_list[i - 1]
    

    for m in array[::-1]:
        result[count_list[m] - 1] = m
        count_list[m] -= 1

    return result


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    
    max_elem = int(1e4)
    result = counting_sort(A=array, max_occurance=max_elem)
    print(*result)

Solution (Python):




import sys


def counting_sort(A, max_occurance):
    result = [0] * array_length
    count_list = [0] * max_occurance

    for j in range(array_length):
        count_list[A[j]] += 1
    

    for i in range(1, max_occurance):
        count_list[i] += count_list[i - 1]
    

    for m in array[::-1]:
        result[count_list[m] - 1] = m
        count_list[m] -= 1

    return result


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    assert len(array) == array_length
    max_elem = int(1e4)
    result = counting_sort(A=array, max_occurance=max_elem)
    print(*result)

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


if __name__ == '__main__':
    
    
    
    array_size = int(input())
    A = [int(x) for x in input().split(' ')]
    A.insert(0, 9999999)
    B = A[:]

    
    counting_sort(A, B, k)

    
    
    print('{0}'.format(' '.join(map(str, B[1:]))))

Solution (Python):

def CountingSort(array,maxval):
    m=maxval+1
    count=[0]*m
    for a in array:
        count[a]+=1
    i=0
    for a in range(m):
        for c in range(count[a]):
            array[i]=a
            i+=1
    return array

if __name__ == '__main__':
    maxval = 2000000
    n = int(input())
    a = [int(i) for i in input().split()]
    print(" ".join([str(s) for s in CountingSort(a,max(a))]))

Solution (Python):

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

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

    for i in range(1, 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

n = int(input())
A = [int(a) for a in input().split()]
B = [0] * n

CountingSort(A, B, 10000)

print(*B)

Solution (Python):
def CountingSort(A, k):
    C = [0] * k
    B = C[:]
    for a in A:
        C[a] += 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]]] = A[i]
        C[A[i]] -= 1
    return B



if __name__ == '__main__':
    N = int(input())
    A = [int(i) for i in input().strip().split()]
    sorted_A = CountingSort(A, int(3E6))
    print(' '.join([str(a) for a in sorted_A[1:len(A) + 1]]))

Solution (Python):
def CountingSort(A, B, k):
    C = [0]*(k+2)
    for i in range(n):
        C[A[i]] += 1
    for i in range(1,k+1):
        C[i] = C[i] + C[i-1]
    x = list(range(n))
    x.reverse()
    for i in x:
        B[C[A[i]]] = A[i]
        C[A[i]] -= 1
    return B
n = int(input())
A = list(map(int,input().split()))
B = [0]*(n+1)
k = max(A)
res = CountingSort(A, B, k)
print(*res[1:])

Solution (Python):
def countingSort(A,B):
    k = max(A)
    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]   
    for j in range(len(A)):
        B[C[A[j]]-1] = A[j]
        C[A[j]] -=1

n = int(input())
A = list(map(int,input().split()))
B = [0]* len(A)
countingSort(A,B)
print(*B)

Solution (Python):
def countint_sort(A, k):
  B = [0] * (len(A))
  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] + C[i - 1]
  for j in range(len(A)):
    ib = C[A[j]] - 1
    B[ib] = A[j]
    C[A[j]] -= 1
  return B

n = int(input())
A = list(map(int, input().split()))
print(" ".join(map(str, countint_sort(A, max(A)))))

Solution (Python):
def countingSort(a,n):
    count = [0]*(max(a)+1)
    for k in a:
      count[k] += 1
    for i in range(len(count)-1):
      count[i+1] += count[i]
    
    sorted_a = [0]*n

    for k in a[::-1]:
        sorted_a[count[k]-1] = k
        count[k] -= 1
    return sorted_a

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

Solution (Python):
def CountingSort(A, B, k):
    C = [0 for i in range(k+1)]
    n = len(A)
    
    for j in range(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]:
        B[C[A[j]]-1] = A[j]
        
        C[A[j]] -= 1


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

Solution (Python):
def CountingSort(A, n, B, k):
  C = [0]*(k+1)

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

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

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

def main():
  n = int(input())
  A = list(map(int, input().split()))
  B = [0]*n
  CountingSort(A, n, B, max(A))
  print(" ".join(map(str, B)))

if __name__ == "__main__":
  main()

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

n = int(input())
A = list(map(int, input().split()))
k = max(A)
B =CountingSort(A, k)
print(" ".join(map(str,B)))

Solution (Python):
def counting_sort(array, maxval):
    m = maxval + 1000
    count = [0] * (m)
    for a in array:
        count[a] += 1
    i = 0
    for a in range(m):
        for c in range(count[a]):
            array[i] = a
            i += 1
    return array
 
if __name__ == '__main__':
    N = int(input())
    l = list(map(int, input().split()))
    a = 0
    li = counting_sort(l, N)
    for a in range(N-1):
        print(li[a], end=" ") 
    print(li[N-1])

Solution (Python):
def counting_sort(array, maxval):
    m = maxval+100
    count = [0] * (m)
    for a in array:
        count[a] += 1
    i = 0
    for a in range(m):
        for c in range(count[a]):
            array[i] = a
            i += 1
    return array
 
if __name__ == '__main__':
    N = int(input())
    l = list(map(int, input().split()))
    a = 0
    li = counting_sort(l, N)
    for a in range(N-1):
        print(li[a], end=" ") 
    print(li[N-1])

Solution (Python):


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

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

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

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

    return B


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

B = counting_sort(A, B, k)
print(*B)

Solution (Python):
def main():
    n = input()
    A = map(int,raw_input().split())
    B = [0]*n
    k = max(A)
    CountingSort(A,B,k,n)

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


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

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

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

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


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
A = [int(i) for i in input().split()]
B = [0] * n
k = max(A)
C = [0] * (k + 1)
for i in range(0, n):
    C[A[i]] += 1
for i in range(1, k + 1):
    C[i] += C[i - 1]
for i in range(n - 1, -1, -1):
    C[A[i]] -= 1
    B[C[A[i]]] = A[i]
print(*B)

Solution (Python):
def CountingSort(A, B, k):
    C = [0 for i in range(k+2)]
    
    for j in range(n):
        C[A[j]] += 1
        
    for i in range(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

if __name__=="__main__":
    n = int(input())
    D = list(map(int, input().split()))
    l = max(D)
    E = D[:]
    CountingSort(D, E, l)
    print(" ".join(map(str, E)))

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


if __name__ == '__main__':
	n = int(input())
	A = [int(s) for s in input().split()]
	B = A[:]
	counting_sort(A, B, max(A))
	print(*B)

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

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


    
    for i in range(k):

        C[i] = C[i] + C[i-1]

    for j in reversed(range(n)):

        B[C[A[j]]] = A[j]
        C[A[j]] -= 1

def main():
    """ ????????? """
    num = int(input().strip())
    A = list(map(int,input().split()))
    max = 0
    for i in range(num):
        if max < A[i]:
            max = A[i]
    if max < num:
        max = num
    max += 2
    B = [0 for i in range(num + 2)]
    CountingSort(A, B, max, num)
    print(" ".join(map(str,B[1:num+1])))

if __name__ == '__main__':
    main()

Solution (Python):
n = int(raw_input())
a = map(int, raw_input().split())

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

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

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


b = [0 for i in range(n)]
k = max(a)
CountingSort(a, b, k)
print ' '.join(map(str, b))

Solution (Python):
def CountingSort(A, B, k):
    C = [0] * (k + 1)
    for a in A: C[a] += 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]] - 1] = A[j]
        C[A[j]] += -1
    
n = int(input())
A=[int(i) for i in input().split()]
B = [None] * n
CountingSort(A, B, max(A))
print(' '.join(map(str,B)))

Solution (Python):
def sort(a, k):
    c = [0]*k
    for x in a:
        c[x] += 1
    b = []
    for i in range(len(c)):
        y = c[i]
        for _ in range(y):
            b.append(i)
    return b

n = int(raw_input())
a = map(int, raw_input().split(' '))
b = sort(a, 10001)

print ' '.join(map(str, b))

Solution (Python):
def countingsort(A,n):
    k=max(A)
    
    B=[0 for i in range(n)]
    C=[0 for i in range(k+1)]
    
    for i in range(n):
        C[A[i]]+=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]]-1]=A[j]
        C[A[j]]-=1
    
    print(*B)
    
n=int(input())
A=list(map(int,input().split()))

countingsort(A,n)

Solution (Python):
def CountingSort(A):
    B = [0]*len(A)
    maxnumber = 0
    for n in range(len(A)):
        if maxnumber < A[n]:
            maxnumber = A[n]
    C = [0]*(maxnumber + 1)

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

    for s in range(len(A))[::-1]:
        B[C[A[s]]-1] =A[s]
        C[A[s]] -= 1

    return B


if __name__ == '__main__':
    cnt = input()
    A = list(map(int,input().split()))
    Ans = list(map(str,CountingSort(A)))
    print(" ".join(Ans))

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
B = []
C = [0] * 10001
for x in A:
    C[x] += 1
for i, k in enumerate(C):
    B += [str(i)] * k
print(" ".join(B))

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

if __name__ == "__main__":
    input()
    A = list(map(int, input().strip().split()))
    B = counting(A)
    print(" ".join(map(str, B)))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
k = max(a) + 1

b = [0 for i in range(n)]
c = [0 for i in range(k)]

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

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

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

print(*b)

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

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

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

    for i in range(len(C)):
        while True:
            if C[i] != 0:
                B.append(i)
                C[i] -= 1
            else:
                break
    return B

result = counting_sort(a,max(a))
print(*result)

Solution (Python):



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

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

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

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


if __name__ == "__main__":
    n = int(input())
    lst = [int(val) for val in input().split()]
    lst.insert(0, 0)
    result = [0] * (n + 1)
    k = max(lst)
    countingSort(lst, result, k, n)
    result.pop(0)
    print(" ".join([str(val) for val in result]))

Solution (Python):



def countingSort(lst, n):
    cnt_lst = [0] * (max(lst)+1)

    for i in range(0, n):
        cnt_lst[lst[i]] += 1

    i = 0
    result = []
    for j, cnt in enumerate(cnt_lst):
        for _ in range(0, cnt):
            result.append(j)
    return result


if __name__ == "__main__":
    n = int(input())
    lst = [int(val) for val in input().split()]
    result = countingSort(lst, n)
    print(" ".join([str(val) for val in result]))

Solution (Python):
def countingSort(A):
    minA = min(A)
    maxA = max(A)
    C = [0]*10001

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

    for j in range(len(A)-1,-1,-1):
        B[C[A[j]]]=A[j]
        C[A[j]]-=1
    return B

if __name__ == '__main__':
    n = (int)(input())
    A = list(map(int,input().split()))

    B = countingSort(A)
    print(*B[1:])

Solution (Python):
def CountingSort(A, B, k):
	C = []
	for i in xrange(k+1):
		C.append(0)
	for j in xrange(n):
		C[A[j]] += 1
	
	
	
	
	for j in xrange(len(C)):
		for k in xrange(C[j]):
			B.append(j)
	return B

n = int(raw_input())
A = map(int, raw_input().split())
k = max(A)

B = []



B = CountingSort(A, B, k)


for i in range(len(B)):
	if i != len(B)-1:
		print(B[i]),
print B[-1]

Solution (Python):

def counting_sort(input_list: list, upper: int) -> list:
    number = len(input_list)

    
    b = [0 for i in range(number+1)]
    
    counter_list = [0 for i in range(upper+1)]

    for j in input_list:
        counter_list[j] += 1

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

    for j in range(number):
        b[counter_list[input_list[j]]] = input_list[j]
        counter_list[input_list[j]] -= 1

    return b


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    k = 2000000
    a = counting_sort(a, k)
    a.pop(0)

    print(' '.join(map(str, a)))

Solution (Python):
def counting_sort(A, B, k):
    C = [0 for _ in xrange(int(k+1))]
    for i in xrange(n):
        C[A[i]] += 1
    
    for i in xrange(k):
        C[i] = C[i] + C[i-1]
    
    for i in xrange(n-1, -1, -1):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1


n = int(raw_input())
A = map(int, raw_input().split())
B = [0 for _ in xrange(n)]

counting_sort(A, B, 10000)

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

Solution (Python):
def counting_sort(A, B, k):
    C = [0 for _ in xrange(k+1)]
    for a in A:
        C[a] += 1

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

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


n = int(raw_input())
A = map(int, raw_input().split())
B = [0 for _ in xrange(n)]

counting_sort(A, B, 10000)

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

Solution (Python):
def counting_sort(A, B, k):
    C = [0 for _ in xrange(k+1)]
    for a in A:
        C[a] += 1

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

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


n = int(raw_input())
A = map(int, raw_input().split())
B = [0 for _ in xrange(n)]

counting_sort(A, B, 10000)

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

Solution (Python):
def main():
    _ = input()
    li = [int(x) for x in input().split(' ')]
    out = countingSort(li, max(li))
    print(*out)


def countingSort(A, k):
    B = []
    for _ in range(len(A)):
        B.append(0)

    C = []
    for _ in range(k + 1):
        C.append(0)

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

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

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

    return B


main()

Solution (Python):
n = int(input())
def CountingSort(A, B, k):
    C = [0] * (k + 1)
    for j in range(n):
        C[A[j]] += 1
    C[0] -= 1
    for i in range(1, k + 1):
        C[i] += C[i - 1]
    for j in range(n - 1, -1, -1):
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1
A = list(map(int, input().split()))
B = [0] * n
CountingSort(A, B, max(A))
print(*B)

Solution (Python):
n = int(input())
def CountingSort(A, B, k):
    C = [0] * (k + 1)
    for j in range(n):
        C[A[j]] += 1
    C[0] -= 1
    for i in range(1, k + 1):
        C[i] += C[i - 1]
    for j in A[::-1]:
        B[C[j]] = j
        C[j] -= 1
A = list(map(int, input().split()))
B = [0] * n
CountingSort(A, B, max(A))
print(*B)

Solution (Python):
n = int(input())
def CountingSort(A, B, k):
    C = [0] * (k + 1)
    for j in range(n):
        C[A[j]] += 1
    C[0] -= 1
    for i in range(1, k + 1):
        C[i] += C[i - 1]
    for j in A[::-1]:
        B[C[j]] = j
        C[j] -= 1
A = list(map(int, input().split()))
B = [0] * n
CountingSort(A, B, max(A))
print(" ".join(map(str,B)))

Solution (Python):



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

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


if __name__ == '__main__':
    k = 10000
    n = int(input())
    A = [None] + [int(a) for a in input().split(" ")]
    
    B = CountingSort(A, k, n)
    print(" ".join(map(str, B[1:])))

Solution (Python):
def cSort(hoge, k):
    sorted_list = [0] * (len(hoge)-1)
    sorted_list.insert(0, None)
    count_list = [0] * (k+1)
    for i in range(1, len(hoge)):
        count_list[hoge[i]] += 1
    
    for i in range(1, len(count_list)):
        count_list[i] = count_list[i] + count_list[i-1]
    
    for j in range(1, len(hoge))[::-1]:
        sorted_list[count_list[hoge[j]]] = hoge[j]
        count_list[hoge[j]] -= 1
    
    sorted_list.remove(None)
    return sorted_list
    
if __name__ == '__main__':
    _ = input()
    hoge = [int(x) for x in input().split()]
    max_num = max(hoge)
    hoge.insert(0, None)
    print (' '.join([str(x) for x in cSort(hoge, max_num)]))

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

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

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

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
m=10001
B=A[:]
C=[0]*m
for a in A:C[a]+=1
for i in range(1,m):C[i]+=C[i-1]
for j in A[::-1]:B[C[j]-1]=j;C[j]-=1
print(*B)

Solution (Python):
input()
A=list(map(int,input().split()))
B=[]
C=[0]*(max(A)+1)
for a in A:C[a]+=1
i=0
for k in C:B+=[str(i)]*k;i+=1
print(' '.join(B))

Solution (Python):
input()
A=list(map(int,input().split()))
B=[]
C=[0]*(max(A)+1)
for a in A:C[a]+=1
i=0
for k in C:B+=[str(i)]*k;i+=1
print(' '.join(B))

Solution (Python):
input()
A=list(map(int,input().split()))
B=[]
C=[0]*(max(A)+1)
for a in A:C[a]+=1
i=0
for k in C:B+=[str(i)]*k;i+=1
print(' '.join(B))

Solution (Python):
input()
A=list(map(int,input().split()))
B=[]
C=[0]*10001
for a in A:C[a]+=1
i=0
for k in C:B+=[str(i)]*k;i+=1
print(' '.join(B))

Solution (Python):
input()
B=[]
C=[0]*10001
for a in map(int,input().split()):C[a]+=1
i=0
for k in C:B+=[str(i)]*k;i+=1
print(' '.join(B))

Solution (Python):
input()
B,C,i=[],[0]*10001,0
for a in map(int,input().split()):C[a]+=1
for k in C:B+=[str(i)]*k;i+=1
print(' '.join(B))

Solution (Python):
input()
C=[0]*10001
for a in map(int,input().split()):C[a]+=1
B=[];i=0
for k in C:B+=[str(i)]*k;i+=1
print(' '.join(B))

Solution (Python):
input()
C=[0]*10001
for a in map(int,input().split()):C[a]+=1
B=[];i=0
for k in C:B+=[str(i)]*k;i+=1
print(' '.join(B))

Solution (Python):
def s():
 input()
 C=[0]*10001
 for a in map(int,input().split()):C[a]+=1
 B=[];i=0
 for k in C:B+=[str(i)]*k;i+=1
 print(' '.join(B))
if'__main__'==__name__:s()

Solution (Python):
def s():
 input()
 C=[0]*10001
 for a in map(int,input().split()):C[a]+=1
 B=[];i=0
 for k in C:B+=[str(i)]*k;i+=1
 print(' '.join(B))
if'__main__'==__name__:s()

Solution (Python):
def s():
 input()
 C=[0]*10001
 for a in map(int,input().split()):C[a]+=1
 B=[];i=0
 for k in C:B+=[str(i)]*k;i+=1
 print(' '.join(B))
if'__main__'==__name__:s()

Solution (Python):
def s():
 input()
 C=[0]*10001
 for a in map(int,input().split()):C[a]+=1
 B=[];i=0
 for k in C:B+=[str(i)]*k;i+=1
 print(' '.join(B))
if'__main__'==__name__:s()

Solution (Python):
def counting_sort(A, k):
    C = [0 for i in range(k)]

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

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

    B = [None for i in range(len(A))]
    for l in A[::-1]:
        B[C[l]-1] = l
        C[l] -= 1

    return B

input()
a = list(map(int, input().split()))
b = counting_sort(a, 10000)
print(*b)

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


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

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

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

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

    return b

b = countingsort(a, 10000)
print(*b)

Solution (Python):
MAXVAL = 10000


def counting_sort(li):
    """Sort li by counting the number of occurrences of each
    element in li.
    All the elements in li are supposed to be 0..10000.

    >>> counting_sort([2, 5, 1, 3, 2, 3, 0])
    [0, 1, 2, 2, 3, 3, 5]
    """
    counter = [0] * (MAXVAL+1)

    for e in li:
        counter[e] += 1

    for i in range(1, MAXVAL+1):
        counter[i] += counter[i-1]

    result = [None] * len(li)
    for e in reversed(li):
        counter[e] -= 1
        result[counter[e]] = e

    return result


def run():
    _ = int(input())  
    xs = [int(i) for i in input().split()]

    print(" ".join([str(i) for i in counting_sort(xs)]))


if __name__ == '__main__':
    run()

Solution (Python):
def countingSort(A):
    k = max(A)
    B = [0]
    B.extend(A)
    C = []
    n = len(A)
    for i in range(k + 1):
        C.append(0)

    for j in range(0, n):
        C[A[j]] += 1
    
    for i in range(1, k + 1):
        C[i] += C[i - 1]
    
    for j in range(n - 1, -1, -1):
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1
    print(' '.join(list(map(str, B[1:]))))
    return
N = int(input())
a = list(map(int, input().split()))
countingSort(a)

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

n = int(input())
a = list(map(int, input().split()))
b = [0 for i in range(n)]
countingsort(a, b, max(a) + 1)
print(" ".join(map(str, b)))

Solution (Python):

"""
Created on Thu May  3 22:47:34 2018
ALDS1_6_A
@author: maezawa
"""

n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n+1)]

def counting_sort(a, b, k):
    c = [0 for _ in range(k+1)]
    
    for aj in a:
        c[aj] += 1
    
    for i in range(1, k+1):
        c[i] += c[i-1]
        
    for j in reversed(range(n)):
        
        b[c[a[j]]] = a[j]
        c[a[j]] -= 1
    
k = max(a)    
counting_sort(a, b, k)
print(b[1],end='')
for i in range(2,n+1):
    print(' {}'.format(b[i]), end='')
print()

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

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

    for i in range(1, k):
        C[i] = 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

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

Solution (Python):
maxx = 2000001;
maxnum = 10010;

n=int(input())
A=[int(x) for x in input().split()]  
A.insert(0,0) 
B=[-1 for x in range(n)]
C=[0 for x in range(maxnum)]



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

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

Solution (Python):





import sys

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

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

    print(' '.join(map(str,B)))


MAX_NUM = 10000
n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
count_sort(A, n, MAX_NUM)

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

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    B=[-1 for i in range(n)]
    counting_sort(A,B,max(A)+1)
    print(*B)

Solution (Python):
n = int(input())
A = list(map(int, input().split())) 
B = [0 for i in range(n)] 
C = [0 for i in range(10001)] 

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

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

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

print(' '.join(map(str, B)))

Solution (Python):
n = int(input())
s = list(map(int, input().split()))
k = max(s)
c = [0 for i in range(k+1)]
def counting_sort(a, k):
    global c
    b = [0 for i in range(len(a)+1)]
    for i in range(n):
        c[a[i]] += 1

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

    for i in reversed(range(n)):
        b[c[a[i]]] = a[i]
        c[a[i]] -= 1
    return b
res = counting_sort(s, k)[1:n+1]
print(*res)

Solution (Python):
def counting_sort(ary, bry, k):
    cry = [0 for i in range(k)]

    for j in range(n):
        cry[ary[j]] += 1

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

    for j in range(n - 1, -1, -1):
        bry[cry[ary[j]] - 1] = ary[j]
        cry[ary[j]] -= 1

if __name__ == '__main__':
    n = int(input())
    ary = [int(_) for _ in input().split()]
    bry = [0 for i in range(n)]
    counting_sort(ary, bry, 10 ** 5)
    print(*bry)

Solution (Python):
def counting_sort(A, B, k):
    len_A = len(A)

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

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

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

    for j in range(len_A - 1, -1, -1):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1


n = int(input())
input_list = list(map(int, input().split(' ')))

B = [0 for _ in range(n)]

counting_sort(input_list, B, max(input_list) + 1)

print(*B)