Module select
This module contains the implementation for slice::select_nth_unstable.
It uses an introselect algorithm based on ipnsort by Lukas Bergdoll and Orson Peters,
published at: https://github.com/Voultapher/sort-research-rs/tree/main/ipnsort
The fallback algorithm used for introselect is Median of Medians using Tukey's Ninther for pivot selection. Using this as a fallback ensures O(n) worst case running time with better performance than one would get using heapsort as fallback.
Functions
- max_index Helper function that returns the index of the maximum element in the slice using the given comparator function
-
median_idx
returns the index pointing to the median of the 3
elements
v[a],v[b]andv[c] - median_of_medians Selection algorithm to select the k-th element from the slice in guaranteed O(n) time. This is essentially a quickselect that uses Tukey's Ninther for pivot selection
- median_of_ninthers
- min_index Helper function that returns the index of the minimum element in the slice using the given comparator function
-
ninther
Moves around the 9 elements at the indices a..i, such that
v[d]contains the median of the 9 elements and the other elements are partitioned around it. -
partition_at_index
Reorders the slice such that the element at
indexis at its final sorted position. - partition_at_index_loop