Most algorithms books describe LSD and MSD Radix Sort variations. However, they do not cover in-place variations. Wikipedia does not describe it either. In this blog I describe an in-place MSD Radix Sort. This is a simpler variant to describe than the type I’ve developed and discussed in previous blogs and in my “Practical Parallel Algorithms in C++ and C#” ebook.

MSD Radix Sort Refresher

All MSD Radix Sort algorithms start by examining the most significant bits of the key. For example, if soring an array of unsigned 32-bit keys, they start with the leftmost 8-bits (or so). Each key would be split into digits – i.e. four 8-bit digits. The algorithm would compute a histogram of the most significant digit of each key, by looking at each key and counting how many of them have the most significant digit equal to zero, and how many equal to a one, and so on up to how many equal to 255.

The algorithm then splits the input array into 256 bins, where all array elements whose keys have the most significant digit (MSD) equal to zero, are placed on the left side of the array, followed by all array elements whose keys have the most significant digit equal to one, and so on, until all keys with MSD of 255 are on the right side of the array.

Once the array has been split into these 256 bins – i.e. sorted based on the MSD – the algorithm sorts each bin, with more than one array element in it, based on the next most significant digit. This can be done recursively, but doesn’t have to.

This process continues, for all bins with more than one array element in it, until all digits have been used for sorting.

In-Place

The following description may be easier to understand by looking at the source code.

To accomplish sorting in-place, the algorithm views the array as if it was split into 256 bins. It then processes each of the 256 bins, one bin at a time. If the bin has no array elements in it, then there is nothing to do, and the bin is skipped.

Each bins start index is known from the histogram counts, computed during the histogram counting phase. For each bin, an end index is tracked which indicates the location within the bin where unprocessed elements are – i.e. it’s unknown whether they belong in this bin or not. All elements between the start index and the end index contain processed array elements – i.e. they belong in this bin.

For each bin with at least one array element in it, the first unprocessed element is examined, extracting the most significant digit of that element. This first unprocessed element is at the end index of the bin.

This extracted digit indicates the bin that the element belongs in. This unprocessed element in the current bin is swapped with the first unprocessed element at the end index of the bin where it belongs – i.e. placing it into the bin it belong in, and incrementing its end index. The first unprocessed element in the current bin has now been replaced, and its MSD is examined. It is then swapped into the bin where it belongs, while bringing a new unprocessed element back into the current bin.

At any time, if the current element in the current bin is determined to belong in the current bin, then no swapping is needed, and the end index of the current bin is simply incremented.

This process continues until all of the array elements in the current bin have been processed. Then, we advance to the next bin and process all of its unprocessed array elements, and so on to the next bin, until all unprocessed elements of all bins have been processed.

Another Way

Another method to accomplish In-Place MSD Radix Sort, is to process the entire array from the first to the last index, swapping elements into their bins. The implementation is a bit more complex as well as the explanation.