Counting Sort

Problem

Sort a list of non-negative integers in ascending order and return the sorted list using counting sort.

Count occurrences of each value into a table indexed by value, then rebuild the output by appending each value as many times as it was counted. This runs in O(n + max value) time; assume all values are non-negative integers.

Hint

The value itself is the index into the count table, so no comparisons are needed.

Test cases

case 1

in: [[4,2,2,8,3,3,1]]

expected: [1,2,2,3,3,4,8]

case 2

in: [[0]]

expected: [0]

case 3

in: [[]]

expected: []

case 4

in: [[5,0,5,0]]

expected: [0,0,5,5]

Starter codePython

def counting_sort(arr):
    # Your code here
    pass

4 test cases · run your code against them in the editor