Counting Sort

Tags: algorithm comp-sci

Is a linear time stable sorting algorithm that works by [see page 15, counting] the number of occurrences in the input array. Assuming the values to be sorted are non-negative integers in the range \( \{ 0, \ldots, k \} \) counting sort keeps an array \( C[0 \ldots k] \) to count elements and an array \( B[1 \ldots n] \) to write the sorted array back.

Formulation

def counting_sort(arr):
    k = max(arr)
    out = [0 for _ in arr]
    mem = [0 for _ in range(k)]
    for j in range(len(arr)):
	mem[arr[j]] += 1
    for i in range(1, k):
	mem[i] = mem[i] + mem[i - 1]
    for j in reversed(range(len(arr))):
	mem[arr[j]] -= 1
	out[mem[arr[j]]] = arr[j]

Code Snippet 1: Counting sort implementation. alg:counting_sort

You can see the implementation of counting sort in alg:counting_sort. The array mem contains the count of each element of the array. The second for loop of the implementation turns count into a prefix-sum array. It makes it so that the each index of count array holds the index/position of where that index should be placed in the sorted array. Then we simply iterate from the end of the input array to the front, placing values where the prefix-sum states they go (decrementing the sum along the way).

For example consider an array \( [3, 4, 3, 1] \). After the first for loop our count array would be \( [0, 1, 0, 2, 1] \). After the prefix-sum calculation mem would be \( [0, 1, 1, 3, 4] \). To build the sorted output array we iterate from the end of the input array and then place each element where its prefix-sum count states it should be. In this case:

The last value is \( 1 \), \( mem[1] = 1 \) so we place a \( 1 \) at \( out[0] \) and set \( mem[1] = 0 \).
The next element is \( 3 \), \( mem[3] = 3 \) so \( out[2] = 3 \) and \( mem[3] = 2 \).
The next element is \( 4 \), \( mem[4] = 4 \) so \( out[3] = 4 \) and \( mem[4] = 3 \).
The last element is \( 3 \), \( mem[3] = 2 \) so \( out[1] = 3 \) and \( mem[3] = 1 \).