Counting-Based Sorting

Learn about counting-based sorting algorithms.

In this lesson, we study two sorting algorithms that are not comparison based. Specialized for sorting small integers, these algorithms elude the lower bounds of Theorem 1 in the previous lesson by using (parts of) the elements in as indexes into an array. Consider a statement of the form

c[a[i]]=1c[a[i]] = 1

This statement executes in constant time, but has c.length possible different outcomes, depending on the value of a[i]. This means that the execution of an algorithm that makes such a statement cannot be modeled as a binary tree. Ultimately, this is the reason that the algorithms in this section are able to sort faster than comparison-based algorithms.

Counting-sort

Suppose we have an input array a consisting of nn integers, each in the range 0,...,k10,...,k − 1. The counting-sort algorithm sorts aa using an auxiliary array c of counters. It outputs a sorted version of a as an auxiliary array b.

The idea behind counting-sort is simple: for each i{0,...,k1}i \in \{0,...,k − 1\}, count the number of occurrences of i in a and store this in c[i]. Now, after sorting, the output will look like c[0] occurrences of 0, followed by c[1] occurrences of 1, followed by c[2] occurrences of 2,...,2,. . . , followed by c[k − 1] occurrences of k − 1.

Visual demonstration of counting-sort

The code that does this is very slick, and its execution is illustrated below:

Press + to interact
The operation of counting-sort on an array of length n = 20 that stores integers 0,...,k − 1 = 9
The operation of counting-sort on an array of length n = 20 that stores integers 0,...,k − 1 = 9

The implementation of the countingSort() method is:

Press + to interact
countingSort(array<int> &a, int k) {
array<int> c(k, 0);
for (int i = 0; i < a.length; i++)
c[a[i]]++;
for (int i = 1; i < k; i++)
c[i] += c[i-1];
array<int> b(a.length);
for (int i = a.length-1; i >= 0; i--)
b[--c[a[i]]] = a[i];
a = b;

Counting-sort analysis

The first for loop in this code sets each counter c[i] so that it counts the number of occurrences of i in a. By using the values of a as indices, these counters can all be computed in O(n)O(n) time with a single for loop. At this point, we could use c to fill in the output array b directly. ...