Counting-Based Sorting

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

$$c[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 $n$ integers, each in the range $0,...,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 \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,. . . ,$ 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: