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\}$ ...