Counting-Based Sorting

Learn about counting-based sorting algorithms.

In this section, 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 a as indexes to 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 a 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, \dots , 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
int[] countingSort(int[] a, int k) {
int c[] = new int[k];
for (int i = 0; i < a.length; i++)
c[a[i]]++;
for (int i = 1; i < k; i++)
c[i] += c[i - 1];
int b[] = new int[a.length];
for (int i = a.length - 1; i >= 0; i--)
b[--c[a[i]]] = a[i];
return b;
}

Counting-sort analysis

The first for loop in this code sets each counter c[i] such that it counts the number of occurrences of i in a. By using the values of a as indexes, 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. However, this would not work if the elements of a have associated data. Therefore we spend a little extra effort to copy the elements ...