I’ve written many blogs and a book on sorting. There is a closely related algorithm called Selection, which provides the k-th element from an unsorted array. For example, a 17-th highest test score from a college Physics class, or a 91-st most popular book at the library.

One way to accomplish Selection is to sort the array and then access the k-th array element. For comparison-based sorting algorithms, such as C++ sort() or C# Array.Sort(), this will take O(NlgN) time. Using Radix Sort, this will take O(N) for constant length keys and can be in-place, without using comparisons.

Selection algorithms can accomplish the job much faster while performing less work, in O(N) expected time for some, with others reaching O(N) worst-case time, for comparison-based and non-comparison algorithms. One such O(N) linear-time non-comparison algorithm is described in this blog – Radix Selection.

Several popular algorithms books describe two variations of Selection: QuickSelect and Median-of-Medians Selection. QuickSelect is in-place, is O(N) expected time and O(N²) in worst-case, which can be made unlikely. Median-of-Medians Selection is amazing, is more complex, and is O(N) worst-case. Implementation of both is included in the latest release of my C# nuget package, HPCsharp, on nuget.org, which is open source and free.

Radix Selection, which also goes by Radix-based Selection, is not mentioned in popular algorithms books, rarely comes up in research papers, yet is a natural simplification to the MSD Radix Sorting algorithm, yielding substantially higher performance – about 7X faster that other Selection algorithms. It is O(N) linear-time, is in-place, is fairly simple and should parallelize well. It is not comparison-based, like other Radix-based algorithms.

Performance of Selection Algorithms

The following Table compares performance of three Selection algorithms to the standard C# Array.Sort when operating on an array with 1 million random 32-bit integers, running on Intel Core Ultra 9 275HX laptop processor:

The following Table compares performance for an array of 1 million presorted 32-bit integers:

The following Table compares performance for an array of 1 million constant 32-bit integers:

QuickSelect with random pivot and Radix Select are always faster than Array.Sort, while Median-of-Medians is double the performance. Radix Select provides the highest performance gain for random arrays because at each pass it splits the array into 256 bins versus QuickSelect’s two “halves”, thus converging on the result much faster. Radix Select is always at least 2X faster than LSD Radix Sort. Median-of-Medians is only slightly faster or nearly the same performance as sorting for other input distributions.

Example Implementation

Radix Selection algorithm implementation is available in the HPCsharp repository: https://github.com/DragonSpit/HPCsharp/blame/master/HPCsharp/SelectionRadix.cs

Some Thoughts on Selection

Selection algorithms can do less work because the only thing they care about to determine k-th element of an unsorted arrays is that all elements to the left of k-th element are less than or equal to the k-th element, and all elements to the right of k-th element are greater than or equal to it. Selection does not care that elements to the left and to the right are sorted.

This may be the reason why Selection is closer to the Minimum or Maximum problem, which determines the minimum or maximum element of an unsorted array in O(N) linear time, than it is to sorting which does much more work. When determining the minimum element all we care about is that all other elements of the unsorted array are larger than the minimum element.

It’s common for Selection algorithms to work with arrays of distinct elements only, requiring extra work to support duplicates. However, Radix Select supports duplicates naturally since they will end up within the same bin.

Parallel Radix Selection

Even parallelization of just the counting portion of the Radix Selection algorithm yielded encouraging results with about 50% for random array and over 3X for constant array. More results to come…

How Radix Selection Works

MSD Radix Select works on array elements one digit at a time, starting from the most significant digit (MSD). For instance, if an array of integers is being sorted, then the most significant digit of each array element is examined, counting how many 9’s there are, 8’s there are, 7’s and so on, until 0’s – for decimal number representation.

Once it is known how many elements have a 9 in the most significant digit, and 8 in the most significant digit and so on, the size of these bins is known, and the starting and ending array index for each of these bins can be computed. Since we are selecting a k-th element of the array, then it’s know which bin the k-th element is in. This is the only bin that needs to be populated with its elements, in its target location. The rest of the array elements are not needed and can be ignored.

To gather all of the array elements that belong in the target bin (with the k-th element inside it) we start on the left side of the array, looking for an element that belongs in the target bin. Once we find one, we look inside the target bin for the first element that does not belong in this bin. The element outside of the bin is then written into the bin, overwriting the element that does not belong. This process continues until all array elements to the left of the bin have been moved inside the bin.

Now, the array to the right of the target bin is scanned for elements that belong inside the bin, until the end of the array has been reached. As elements that belong are found they are moved inside the bin by scanning inside the bin for elements that don’t belong and pairing them up with elements outside the bin which belong.

Once the target bin has all of the elements that belong in it has been assembled, by moving (and not swapping) elements from the outside of the bin that belong in the bin, the bin is processed in the same way recursively using the next most significant digit. This process continues until either the target bin (with the k-th index inside it) has a single element or all of the digits have been used and we have run out of digits. Then the k-th element of the array is returned.