The Radix Sort

The radix sort shown below takes a list of integers and puts each element on a smaller list, depending on the value of its least significant byte. Then the small lists are concatenated, and the process is repeated for each more significant byte until the list is sorted. The radix sort is simpler to implement on fixed-length data such as ints, but it is illustrated here using strings.

Two functions perform the radix sort. The function radixSort() performs one pass through the data, performing a partial sort. Line 12 ensures that all the lists in table are empty. The loop on lines 13–24 executes as long as there is something on the input list. Lines 15–22 select which position in the table to put the next string on, based on the value of the character in the string specified by whichByte. If the string has fewer characters than whichByte calls for, the position is 0 (which ensures that the string “an” comes before the string “and”). Finally, lines 25 and 26 concatenate all the elements of table into one big list in table[0].

The function sortStrings() sorts an array of strings by calling radixSort() several times to perform partial sorts. Lines 39–46 create the original list of strings, keeping track of the length of the longest string (because that’s how many times it needs to call radixSort()). Lines 47 and 48 call radixSort() for each byte in the longest string in the list. Finally, lines 49 and 50 put all the strings in the sorted list back into the array. Note that sortStrings() doesn’t free all the memory it allocates.

An implementation of a radix sort.