When you have an an unsorted array and want k-th largest value, Selection algorithm comes to the rescue. No need to sort the array, as that’s too much work and is much slower, but instead Selection can be used. Selection algorithms are in-place, with most at least expected linear-time, and some worst-case linear. In this blog I’ll explore the questions, “Do the current Selection algorithm implementation still do too much work? Which new method performs less work and is significantly faster?”

Current Selection Implementations

Several programming languages provide a standard implementation of Selection:

• C++ has nth_element, which is O(N) worst-case with most recent implementations
• Rust has select_nth_unstable, which is O(N) worst-case
• Python has numpy.partition, which is O(N) worst-case

All of these implementations use comparison-based algorithms, such as QuickSelect with a switch to Median-of-Medians if QuickSelect starts choosing pivots poorly. This guarantees O(N) performance in the worst-case.

Also, all of these implementations perform partitioning on the array to accomplish selection.

From these it may seem like partitioning is a necessary operation to achieve selection, but it is not.

Counter Example

One algorithm which does not partition the array to achieve k-th selection is Radix Selection. Radix Selection splits the array into bins and moves (i.e. without swapping) array elements that belong into the bin where the array[k] element is. Then it continues to refine only that particular bin in the following iterations. It can be implemented non-recursively. Radix Selection does not do anything with elements outside this target bin which don’t belong to the target bin – these outside elements are ignored.

Radix Selection performs no element-to-element comparisons. By doing less work, it performs substantially (many times) higher – as shown in my previous Radix Selection blogs.

Implementations

C# implementation of Radix Select is part of the HPCsharp open source nuget package and repository. C++ implementation is part the ParallelAlgorithms repository.