In this section we study two sorting algorithms that are not comparisonbased. Specialized for sorting small integers, these algorithms elude the lowerbounds 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 countingsort algorithm sorts using an auxiliary array of counters. It outputs a sorted version of as an auxiliary array .
The idea behind countingsort 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:
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[i1]; int b[] = new int[a.length]; for (int i = a.length1; i >= 0; i) b[c[a[i]]] = a[i]; return b; }
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 runningsum 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 countingsort 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.
Countingsort 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 radixsort algorithm, which we now describe, uses several passes of countingsort to allow for a much greater range of maximum values.
Radixsort sorts bit integers by using passes of countingsort 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.
int[] radixSort(int[] a) { int[] b = null; for (int p = 0; p < w/d; p++) { int c[] = new int[1<<d]; // the next three for loops implement countingsort b = new int[a.length]; for (int i = 0; i < a.length; i++) c[(a[i] >> d*p)&((1<<d)1)]++; for (int i = 1; i < 1<<d; i++) c[i] += c[i1]; for (int i = a.length1; i >= 0; i) b[c[(a[i] >> d*p)&((1<<d)1)]] = a[i]; a = b; } return b; }(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 countingsort 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 .
Radixsort performs passes of countingsort. Each pass requires time. Therefore, the performance of radixsort 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.