Algorithm Improvement through Performance Measurement: Part 1

Algorithm Improvement through Performance Measurement: Part 2

Algorithm Improvement through Performance Measurement: Part 3

Algorithm Improvement through Performance Measurement: Part 4

Algorithm Improvement through Performance Measurement: Part 5

The In-place Hybrid MSD N-bit-Radix Sort I presented in In-place Hybrid N-bit-Radix Sort was developed as a combination of Radix Sort, Insertion Sort, and Counting Sort. This algorithm sorts arrays of integers (8, 16, 32, and 64-bit, unsigned and signed), and significantly outperforms STL **sort()**, which is a hybrid combination of QuickSort, Heap Sort, and Insertion Sort. In-place Hybrid MSD N-bit-Radix Sort algorithm uses a recursive Radix Sort technique based on the most-significant-digit (MSD). It sorts based on the MSD first, followed by the next digit and so on until all digits have been used for sorting. The algorithm has a nice property of being in-place (not requiring extra memory), but lacks being stable.

Stable algorithms resolve ties between array elements by placing the element that appeared first in the input array as first in the output array. Stability is not necessary when sorting only numbers, as it is impossible to differentiate the result which was sorted using a stable algorithm from one sorted using a non-stable algorithm. In this article, I develop and optimize a stable version of the MSD Radix Sort since stability is useful in cases of sorting other than only numbers.

### Stable MSD Radix Sort Concept

The following discussion illustrates how an MSD Radix Sort works with decimal numbers. In this case, the radix is 10, and Decimal-Radix sorting is being performed (10-Radix Sort).

Three numbers start with a zero ( 07, 09, 01 ), four numbers start with a one (13, 15, 15, 19), three numbers start with a two (22, 28, 21 ), none start with a three, two numbers start with a four (45, 42).

Use an output array of equal size to the input array, and split it into bins that hold 3 elements, 4 elements, 3 elements, and 2 elements (as we just counted).

Place all numbers that started with zeros into the bin zero, all numbers that started with ones into the bin one, that started with twos into bin two, and so on.

Sort each of these bins based on the second digit

Create an output array of equal size for each input bin:

Place all numbers that have the second digit equal to a one in bin one, all numbers that have the second digit equal to two in bin two, and so on.

Assemble all of the bins together into a single sorted array

Note this procedure took two passes over all of the array elements: one pass for the left-most digit, and the second pass for the second digit; because each element was made of two digits in this example. The algorithm takes two passes over the entire array no matter how many elements are in the array to be sorted. Thus, run time is linear in order, times the number of digits in the elements **-O( dn )**, where **d** is the number of digits and **n** is the number of elements in the array.