Counting Sort
An integer sorting algorithm that operates by counting the number of objects that have each distinct key value.
Ready
Step 0Total -1
1function countingSort(arr):
2 max = findMax(arr)
3 count = new Array(max + 1).fill(0)
4 output = new Array(arr.length)
5
6 for val in arr:
7 count[val]++
8
9 for i from 1 to max:
10 count[i] += count[i-1]
11
12 for i from arr.length-1 down to 0:
13 output[count[arr[i]] - 1] = arr[i]
14 count[arr[i]]--
15
16 return output
Complexity
TimeO(n + k)
SpaceO(k)
Where k is the range of the non-negative key values.