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
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
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
The code that does this is very slick, and its execution is illustrated in
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
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.
-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
and so on until, in the last pass, the integers are sorted by their most
(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.
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.