Subsections

# 11.2 Counting Sort and Radix Sort

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 11.5 by using (parts of) the elements in as indices into an array. Consider a statement of the form This statement executes in constant time, but has possible different outcomes, depending on the value of . This means that the execution of an algorithm that makes such a statement cannot be modelled as a binary tree. Ultimately, this is the reason that the algorithms in this section are able to sort faster than comparison-based algorithms.

## 11.2.1 Counting Sort

Suppose we have an input array consisting of integers, each in the range . The counting-sort algorithm sorts using an auxiliary array of counters. It outputs a sorted version of as an auxiliary array .

The idea behind counting-sort is simple: For each , count the number of occurrences of in and store this in . Now, after sorting, the output will look like occurrences of 0, followed by occurrences of 1, followed by occurrences of 2,..., followed by occurrences of . The code that does this is very slick, and its execution is illustrated in Figure 11.7:  The first loop in this code sets each counter so that it counts the number of occurrences of in . By using the values of as indices, these counters can all be computed in time with a single for loop. At this point, we could use to fill in the output array directly. However, this would not work if the elements of have associated data. Therefore we spend a little extra effort to copy the elements of into .

The next loop, which takes time, computes a running-sum of the counters so that becomes the number of elements in that are less than or equal to . In particular, for every , the output array, , will have Finally, the algorithm scans backwards to place its elements, in order, into an output array . When scanning, the element is placed at location and the value is decremented.

Theorem 11..7   The method can sort an array containing integers in the set in time.

The counting-sort algorithm has the nice property of being stable; it preserves the relative order of equal elements. If two elements and have the same value, and then will appear before in . This will be useful in the next section.

Counting-sort is very efficient for sorting an array of integers when the length, , of the array is not much smaller than the maximum value, , that appears in the array. The radix-sort algorithm, which we now describe, uses several passes of counting-sort to allow for a much greater range of maximum values.

Radix-sort sorts -bit integers by using passes of counting-sort to sort these integers bits at a time.11.2 More precisely, radix sort first sorts the integers by their least significant bits, then their next significant bits, and so on until, in the last pass, the integers are sorted by their most significant bits. (In this code, the expression extracts the integer whose binary representation is given by bits of .) An example of the steps of this algorithm is shown in Figure 11.8. This remarkable algorithm sorts correctly because counting-sort is a stable sorting algorithm. If are two elements of , and the most significant bit at which differs from has index , then will be placed before during pass and subsequent passes will not change the relative order of and .

Radix-sort performs passes of counting-sort. Each pass requires time. Therefore, the performance of radix-sort is given by the following theorem.

Theorem 11..8   For any integer , the method can sort an array containing  -bit integers in time.

If we think, instead, of the elements of the array being in the range , and take we obtain the following version of Theorem 11.8.

Corollary 11..1   The method can sort an array containing integer values in the range in time.

#### Footnotes

... time.11.2
We assume that divides , otherwise we can always increase to .
opendatastructures.org