nth

Fast and memory efficient implementation of a Selection Algorithm in Go.

After calling nth.Element(data sort.Interface, n int) everything before index n will be less than data[n] and everything after n will be greater than or equal to data[n]. IE it partially sorts data such that data[n] == sortedData[n].

nth.Element is an implementation of QuickSelectAdaptive from Andrei Alexandrescu's 2016 paper Fast Deterministic Selection. It is has a deterministic O(n) runtime, O(1) space usage. Classical implementations of Selection Algorithms usually rely on non-determinism (random pivots) or have high constant factors (median-of-median pivots), or are not as fast as this algorithm (IntroSelect).

The name nth.Element is inspired from C++'s nth_element, which is also an implementation of a Selection Algorithm (although most STL implementations use IntroSelect).

Note: This is not a complete implementation yet, although already should be faster than just using sort.Sort.