Counting Sort

Counting Sort algorithm based on using keys of a specific range. It works by counting the number of values in given array with a key value and storing it in an array or map by this key.

Lets understand it with example:

arr = [4, 3, 1, 6, 9, 0, 1, 0, 2, 2]

indexes = [0 1 2 3 4 5 6 7 8 9] – key values, indexes of array

counts => [2 2 2 1 1 0 1 0 0 1] – number of elements with index value in array arr.

So you create additional array [2, 2, 2, 1, 1, 0, 1, 0, 0, 1].

Then, you can traverse it and get all elements in sorted order, since array indexes are sorted already.

Counting sort works only for arrays with non-negative integer values. For other cases, you can use dict() or any other ordered data structure.

Time complexity: O(max(N, max(arr)) - to traverse two arrays: first one of size N and second array of size max(arr).

Space complexity: O(max(arr)) - to create additional array.