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 CountingSort(n, input_line, max_num):
    max_num += 1
    count_list = [0 for i in range(max_num)]
    output_line = [0 for i in range(n)]
    for i in range(n):
        count_list[input_line[i]] += 1
    for i in range(1,max_num):
        count_list[i] = count_list[i] + count_list[i-1]
    for i in range(n-1,-1, -1):
        output_line[count_list[input_line[i]]-1] = str(input_line[i])
        count_list[input_line[i]] -= 1
    return output_line

n = int(input())
input_line = [int(i) for i in input().split()]
max_num = max(input_line)
output_line = CountingSort(n, input_line, max_num)
print(' '.join(output_line))

Solution (Python):
def counting_sort(a, b, k):
    c = [0 for _ 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-1]

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


def print_list_split_whitespace(a):
    for x in a[:-1]:
        print(x, end=" ")
    print(a[-1])


n = int(input())
a = [int(x) for x in input().split()]
b = a.copy()
k = max(a)

counting_sort(a, b, k)

print_list_split_whitespace(b)

Solution (Python):
def counting_sort(A, B, k):
    C = {i: 0 for i in range(k+1)}

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

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

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

def print_list(B):
    for i, j in enumerate(B):
        if i == n - 1:
            print(j)
        else:
            print(j, end=" ")

n = int(input())
A = [int(e) for e in input().split()]
B = [0 for i in range(n)]
counting_sort(A, B, max(A))
print_list(B)

Solution (Python):
def main():
    n = int(input())
    numbers = list(map(int, input().split()))
    counters = [0] * 10001
    sortedNumbers = [0] * n
    for number in numbers:
        counters[number] += 1

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

    for i in range(n - 1, -1, -1):
        sortedNumbers[counters[numbers[i]] - 1] = numbers[i]
        counters[numbers[i]] -= 1

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

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())
    numbers = list(map(int, input().split()))
    counters = [0] * 10001
    sortedNumbers = [0] * n
    for number in numbers:
        counters[number] += 1

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

    for i in range(n - 1, -1, -1):
        sortedNumbers[counters[numbers[i]] - 1] = numbers[i]
        counters[numbers[i]] -= 1

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

if __name__ == '__main__':
    main()

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

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

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

    for j in range(0, n)[::-1]:
        B[C[A[j]] - 1] = A[j]
        C[A[j]]-=1
    return B
        
print(' '.join(map(str, countingSort(A, [0] * n, 10000))))

Solution (Python):
def countingsort(A, k):
    C = [0 for i in range(k+1)]
    B = [0 for i in range(len(A))]
    for e in A:
        C[e] += 1
    for i in range(1, k+1):
        C[i] += C[i-1]
    for e in A[::-1]:
        B[C[e]-1] = e
        C[e] -= 1
    return B
    
n = input()
x = map(int, raw_input().split())

x = countingsort(x, max(x))

for e in x:
    print e,

Solution (Python):

from __future__ import division, print_function
from sys import stdin
from collections import Counter


def counting_sort(a, b, k):
    c = Counter()
    for j in a:
        c[j] += 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


n = int(stdin.readline())
data = [int(s) for s in stdin.readline().split()]
output = [0] * (n+1)
counting_sort(data, output, 10000)
print(*output[1:])

Solution (Python):



import time
import sys
import io
import re
import math
start = time.clock()
i = 0
n=int(raw_input())
A=map(int, raw_input().split())
A.sort()
print ' '.join(map(str,A))

Solution (Python):
def CountingSort(A, B, k):
    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]-1] = j
        C[j] -= 1


n = int(input())
inlst = list(map(int, input().split()))
k = max(inlst)
outlst = [0]*n
CountingSort(inlst, outlst, k)
print(*outlst)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
A = [int(x) for x in input().split()]
C = [0] * 10001
B = [0] * (n)
for a in A:
    C[a] += 1
for i in range(1, 10001):
    C[i] += C[i-1]
    if C[i] == n:
        break
for a in A[::-1]:
    B[C[a]-1] = a
    C[a] -= 1
print(*B)

Solution (Python):




import sys
input = sys.stdin.buffer.readline

n = int(input())
A = [int(i) for i in input().split()]
B = [None] * n
C = [0] * 10001

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

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

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

print(" ".join([str(b) for b in 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,k+1):
        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
    return B

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

for i in range(len(B)):
    if i<len(B)-1:
        print(B[i],end=' ')
    else:
        print(B[i])

Solution (Python):

def countingSort(A, B, k, n):
    c = [0] * (k+1)
        
    for i, a in enumerate(A):
        c[a] += 1

    for i in range(1, k+1):
        c[i] = c[i] + c[i-1]
        
    for j, a in enumerate(reversed(A)):
        B[c[a]-1] = a
        c[a] -= 1
        
    print(*b)
    return

import sys
import copy
n = int(input())
a = list(map(int, sys.stdin.readline().split()))
b = [0] * n
k = max(a)

countingSort(a, b, k, n)

Solution (Python):
n = int(input())
a = [int(x) for x in list(input().split())]
b = [0] * (n + 1)
c = [0] * 10001
k = max(a)


for i in a:
    c[i] += 1


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

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

print(*b[1:])

Solution (Python):
def main():
    n = int(input())
    A = list(map(int,input().split()))
    B = [0]*(len(A))
    

    A1 = A
    A1.sort(reverse = True)

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

    
    for i in range(len(C)):
        if i == 0:
            continue
        else:
            C[i] += C[i-1]
    

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

    return B

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

Solution (Python):
def countingSort(A,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]+C[i-1]
    B=[0 for i in range(len(A))]
    for i in A:
        x=C[i]
        B[x-1]=i
        C[i]-=1
    return B
n=int(input())
a=[int(i)for i in input().split()]
b=countingSort(a,10000)
print(" ".join(map(str,b)))

Solution (Python):
def counting_sort(A):
    B = A.copy()
    C = [0 for _ in range(max(A) + 1)]
    
    for num in A:
        C[num] += 1
    for index in range(1, len(C)):
        C[index] = C[index] + C[index-1]

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

num = int(input())
arr = list(map(int, input().split()))
arr = counting_sort(arr)
print(" ".join(map(str, arr)))

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

SIZE = 10001
max = max(A)

C = [0] * SIZE
B = [None]* n
for i in range(len(A)):
    C[A[i]] += 1

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

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

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

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def counting_sort(A, B, C, K, N):
    
    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 reversed(range(N)):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    K = max(A)
    B = [0] * N
    C = [0] * (K + 1)

    counting_sort(A, B, C, K, N)
    print(*B)


if __name__ == '__main__':
    main()

Solution (Python):
def countingSort(A, k=None):
    if not k:
        k = max(A)
    C = [ 0 for i in range(k+1)]
    for j in range(len(A)):
        C[A[j]] += 1
    total = 0
    for k in range(len(C)):
        total += C[k]
        C[k] = total
    B = [ 0 for l in range(len(A))]
    for _A in A[::-1]:
        B[C[_A]-1] = _A
        C[_A] -= 1
    return B


if __name__ == '__main__':
    n = int(input())
    A = list(map(int, input().rstrip().split()))
    print(' '.join(map(str,countingSort(A))))

Solution (Python):
def countingSort(a,m):
    m += 100
    cnt = [0]*m
    for i in a:
        cnt[i] += 1
    i = 0
    for b in range(m):
        for c in range(cnt[b]):
            a[i] = b
            i+=1
    return a
n = int(input())
a = countingSort(list(map(int,input().split())),n)
print(*a)

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

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

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

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

    return B


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

    B = counting_sort(A, n, 10000)
    print(*B)


if __name__ == "__main__":
    main()

Solution (Python):
def countingSort(A):
    max_a = max(A)
    C = []
    for i in range(max_a+1):
        C.append(0)

    for a in A:
        C[a] += 1
    cum_sum = 0
    for i in range(max_a+1):
        cum_sum += C[i]
        C[i] = cum_sum
        
    B = []
    for _ in range(len(A)):
        B.append(None)
    for a in A[::-1]:
        B[C[a]-1] = a
        C[a] -= 1
    return B

_ = input()
A = list(map(int, input().rstrip().split(" ")))
B = countingSort(A)
print(" ".join(list(map(str, B))))

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

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]+C[i-1]

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

countingSort(A,B,max(A))
print(*B)

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 - 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, input().split()))

k = max(A) + 1
B = [0 for _ in range(n)]


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

Solution (Python):
import sys


def main():
    N = int(sys.stdin.readline())
    A = [int(x) for x in sys.stdin.readline().split()]

    C = [0] * (max(A) + 1)

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

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

    B = [None] * N

    

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

    print(" ".join(list(str(x) for x in B)))


main()

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

b = [0] * n
c = [0] * (MAXAI + 1)
for i in range(n):
    c[a[i]] += 1
for i in range(1, MAXAI + 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

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

Solution (Python):

from typing import List, Callable


def counting_sort_destructive(L: List[int], k: int, key: Callable[[int], int] =lambda x: x) -> None:
    """
    counting_sort() の破壊関数版

    Args:
        L (list)
        k (int): L の要素は 0 to k であると仮定する
        key (function): key が指定されている場合、key を L の各要素に適用してからソートを行う

    Raises:
        ValueError: L の要素のいずれかが 0 <= x <= k を満たしていなかった場合

    Examples:
        >>> seq = [1, 3, 5, 10, 4, 6, 15, 7, 2, 0] 
        >>> counting_sort_destructive(seq, 15)    
        >>> seq
        [0, 1, 2, 3, 4, 5, 6, 7, 10, 15]
    """
    if any(map(lambda x: key(x) < 0 or key(x) > k, L)):
        raise ValueError(f"counting_sort_destructive(): key(x) (x: element of L) should be 0 <= key(x) <= k. got k: {k}")

    n = len(L)
    accum_sum_memo = [0] * (k + 1)    

    for i in range(n):
        accum_sum_memo[key(L[i])] += 1
    for i in range(1, k+1):
        accum_sum_memo[i] += accum_sum_memo[i-1]
    
    tmp = tuple(L)    
    for j in range(n-1, -1, -1):
        L[accum_sum_memo[key(tmp[j])] - 1] = tmp[j]
        accum_sum_memo[key(tmp[j])] -= 1    





def radix_sort(L: List[int], bucket_bit_size: int=8) -> None:
    """
    bucket_size = 2 ** bucket_bit_size とする (除算を避けビットシフトのみで実装するため、bucket_size は 2 の冪を仮定している)
    O(digit_length * (n + bucket_size)) で L を安定的かつ破壊的に基数ソートする (digit_length = log(n, bucket_size) である)
    
    Args:
        L (list)
        bucket_bit_size (int): L の各値を何 bit ごとに分けて基数ソートを行うかの値
    
    Raises:
        ValueError: L に負の値が含まれているとき

    Examples:
        >>> seq = [4321, 5500, 8686, 5586, 1234, 1235, 0, 24, 7, 1000000007]
        >>> radix_sort(seq, bucket_bit_size=8)
        >>> seq
        [0, 7, 24, 1234, 1235, 4321, 5500, 5586, 8686, 1000000007]
    """
    if any(map(lambda x: x < 0, L)):
        raise ValueError(f"radix_sort(): element of L should be positive. got L: {L}")
    if L:
        M = max(L)
        
        max_digit_chank = (M.bit_length() + bucket_bit_size - 1) // bucket_bit_size
        
        mask = (1 << bucket_bit_size) - 1    
        for i in range(max_digit_chank):
            key_func = lambda x: (x >> (i * bucket_bit_size)) & mask
            counting_sort_destructive(L, mask, key_func)




if __name__ == "__main__":
    n = int(input())
    L = list(map(int, input().split()))
    radix_sort(L, 16)
    print(*L, sep=' ')

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

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

input()
C = [0]*10_001

for a in map(int, input().split()):
    C[a] += 1
    
B = []
i = 0
for c in C:
    B += [i]*c
    i += 1
print(*B)

Solution (Python):
def countingSort(A, B, k):
    from collections import defaultdict
    C = defaultdict(int)
    for a in A:
        C[a] += 1
    cnt = 0
    for i in range(max(C.keys()) + 1):
        for _ in range(C[i]):
            B[cnt] = i
            cnt += 1


def resolve():
    n = int(input())
    A = [int(i) for i in input().split()]
    B = [0] * n
    countingSort(A, B, max(max(A), n))
    print(*B)

resolve()

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

maxlen = max(A)

C1 = [0] * (maxlen + 1)

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

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

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

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

Solution (Python):
from itertools import accumulate

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

C = [0]*(max(A)+1)
B = [0]*N

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

C = list(accumulate(C))

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

print(*B)

Solution (Python):




def countingSort(A, B, k):
    global n

    C = [0] * k

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

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

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


if __name__ == "__main__":
    n = int(input())
    A = [int(i) for i in input().split()]

    B = [0] * n

    countingSort(A, B, max(A) + 1)
    print(' '.join(map(str, B)))

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    n = I()
    A = LI()

    k = max(A)
    B = [0]*(n+1)

    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] + C[i-1]

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

        print(*B[1:])

    CountingSort(A, B, k)

if __name__ == '__main__':
    resolve()

Solution (Python):
import sys

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

if __name__ == "__main__":
    n = int(input())
    A = [0] + list(map(int,input().split()))
    k = 10000
    B = [0]*(n+1)
    CountingSort(A,B,k)
    print(*B[1:])

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

def counting_sort(nums,n):
    max_nums=max(nums)
    basket=[0 for i in range(max_nums+1)]
    for i in range(n):
        key=nums[i]
        basket[key]+=1

    answer=[]
    for i in range(len(basket)):
        if basket[i]!=0:
            for j in range(basket[i]):
                answer.append(i)
    return answer

answer=counting_sort(nums,n)
print(' '.join(map(str,answer)))

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

for num in A:
    c[num] += 1

for i in range(0, max(A)):
    c[i + 1] += c[i]

for j in range(-1, -n-1, -1):
    output[c[A[j]] - 1] = A[j]
    c[A[j]] -= 1

print(*output)

Solution (Python):



def CountingSort(A):
    MAX = 10000
    B = [0 for e in range(n)]
    C = [0 for e in range(MAX)]
    
    for j in range(n):
        C[A[j]] += 1
    
    for i in range(1,MAX):
        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 = [int(e) for e in input().split()]
print(*CountingSort(A))

Solution (Python):
n = int(input())
A = [int(x) for x in input().split()]

B = [0] * n
C = [0] * 10001

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

j = 0
for i in range(10001):
    for c in range(C[i]):
        B[j] = i
        j += 1

print(' '.join([str(x) for x in B]))

Solution (Python):
def countng_sort(a):
  MAX = 10000
  n = len(a)
  b = [None] * n
  c = [0] * MAX
  
  for i in range(n):
      c[a[i]] += 1
  
  for i in range(1, MAX):
      c[i] += c[i - 1]
  
  for i in reversed(range(0, n)):
      b[c[a[i]] - 1] = a[i]
      c[a[i]] -= 1

  return b

n = int(input())
a = [int(i) for i in input().split()]
print(*countng_sort(a))

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

def countingSort(n,a,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]
    b=[0]*n
    for j in range(n-1,-1,-1):
        b[c[a[j]]-1]=a[j]
        c[a[j]]-=1
    return b

def main(n,a):
    b=countingSort(n,a,10000)
    return b 
    
if __name__=='__main__':
    n,a=readinput()
    ans=main(n,a)
    print(' '.join(map(str,ans)))

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

def countingSort(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-1]
    
    for j in range(len(A)-1, -1, -1):

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

A = countingSort(A, max(A))
print(" ".join([str(s) for s in A]))

Solution (Python):
def countng_sort(a):
  MAX = 10000
  n = len(a)
  b = [None] * n
  c = [0] * MAX
  
  for i in range(n):
      c[a[i]] += 1
  
  for i in range(1, MAX):
      c[i] += c[i - 1]
  
  for i in reversed(range(0, n)):
      b[c[a[i]] - 1] = a[i]
      c[a[i]] -= 1

  return b

n = int(input())
a = [int(i) for i in input().split()]
print(*countng_sort(a))

Solution (Python):
def CountingSort(A,B,k):
    global 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-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,input().split()))
B = [0 for i in range(n)]
CountingSort(A, B, 10000)
print(" ".join(map(str,B)))

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

n = int(input())
A = list(map(int, input().split()))
B = [-1]*n
CountingSort(A, B, max(A))
print(*B)

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())

A = [None] + list(map(int, input().split()))
B = [None]*(n+1)

C = [0]*10001

k = 10000

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

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


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

print(' '.join(map(str, B[1:])))

Solution (Python):
def counting_sort(n, A, k=10001):
    C = [0 for _ in range(k)]
    B = [0 for _ in range(n)]

    for i in range(n):
        C[A[i]] += 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


def main():
    n = int(input())
    A = list(map(int, input().split()))
    print(*counting_sort(n, A))


if __name__ == '__main__':
    main()

Solution (Python):
maxx = 2000001
maxnum = 10010

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

B = [0] * n
C = [0] * maxnum

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


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

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

print(*B)

Solution (Python):
MAX =20000001
VMAX = 10001
INF = 10 ** 10
cnt = 0

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

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

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


n = int(input())
A =[int(x) for x in input().split()]
CountingSort(A, n)

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

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

    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(n-1,-1,-1):
        c = C[A[j]] - 1
        B[c] = A[j]
        C[A[j]] -= 1

    return B

ans = []
ans = countingsort(sort_list,ans,max(sort_list))
print(' '.join([str(i) for i in ans]))

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

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

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

counting_sort(A, B, 10000)
print(" ".join(map(str, B)))

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

k = 10000
out = CountingSort(A,k)

print(*out, sep=" ")

Solution (Python):
def counting_sort(arr):
    max_value = max(arr) + 1
    counter = [0] * max_value

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

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

    sorted_arr = [0] * len(arr)
    for i in range(len(arr)):
        sorted_arr[counter[arr[i]] - 1] = arr[i]
        counter[arr[i]] -= 1
    
    return sorted_arr

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

print(*counting_sort(arr))

Solution (Python):
N =int(input())
A = list(map(int,input().split()))
COUNT = [0]*10000

def cnt_sort(A):
    res = [""] * len(A)
    for a in A:
        COUNT[a]+=1
    for i in range(1,len(COUNT)):
        COUNT[i] = COUNT[i] + COUNT[i-1]
    for a in A:
        res[COUNT[a]-1] = str(a)
        COUNT[a] -=1
    return res

print(" ".join( cnt_sort(A)))

Solution (Python):
N=int(input())
num_list=[int(i) for i in input().split()]
B=[None]*N
def counting(A,B,k):
    C = [0] * k
    for j in range(N):
        C[A[j]]+=1
    for i in range(1,k):
        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
ans=counting(num_list,B,10000)
print(*ans)

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

def counting_sort(A):
    n=len(A)
    K=max(A)
    C=[0]*(K+1)
    for i in range(n):
        C[A[i]]+=1
    
    for i in range(1,K+1):
        C[i]=C[i-1]+C[i]

    ans=[0]*n

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

print(*counting_sort(A))

Solution (Python):
def counting_sort(A, B, k):
    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

n = int(input())
arr = list(map(int, input().split()))
B = [0]*n
counting_sort(arr, B, 10001)
print(*B)

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]

K = 10000
C = [0] * K

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

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

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

print(*B)

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

def counting_sort(arr):
	max_num = max(arr)
	min_num = min(arr)
	count = [0] * (max_num - min_num + 1)
	for ele in arr:
		count[ele - min_num] += 1
	return [ele for ele, cnt in enumerate(count, start=min_num) for _ in range(cnt)]


AA = counting_sort(A)
print(*AA)

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


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

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

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

    return B


print(*counting_sort(A, n, 10000))

Solution (Python):
k = 10**5
c = [0] * k
n = int(input())
A = [int(_) for _ in input().split()]
B = [0] * (n+1)


def CountingSort(A, B, k):
    for i in range(k):
        c[i] = 0

    for j in range(0, 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]]] = A[j]
        c[A[j]] -= 1

CountingSort(A, B, k)
print(" ".join(map(str, B[1:])))

Solution (Python):
def countingsort(A, n, k):
    B = [None for _ in range(n+1)]
    C = [0 for _ in range(k+1)]

    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

    return B

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

    print(' '.join(map(str, countingsort(A, n, k)[1:])))

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

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

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

b = [0 for i in range(n)]
CountingSort(a,b,max(a))
print(*b)

Solution (Python):
N=int(input())
L=list(map(int,input().split()))
L_temp=L

A_N=100010
counter=[0]*A_N

for l in L_temp:
    counter[l]+=1
    
for c_idx in range(1,len(counter)):
    counter[c_idx]+=counter[c_idx-1]

    
L_sort=[0]*len(L_temp)

for l in L_temp[::-1]:
    L_sort[counter[l]-1]=l
    
    counter[l] -= 1
    
print(' '.join(map(str,L_sort)))

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


if __name__ == '__main__':
    main()

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

  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 reversed(range(0, n)):
    B[C[A[j]]] = A[j]
    C[A[j]] -= 1

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

CountingSort(A, B, max(A))
print(*B[1:])