Module select

🔬This is a nightly-only experimental API. (slice_internals)

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.

Constants

INSERTION_SORT_THRESHOLD 🔒 Experimental

Functions

max_index 🔒 Experimental

Helper function that returns the index of the maximum element in the slice using the given comparator function

median_idx 🔒 Experimental

returns the index pointing to the median of the 3 elements v[a], v[b] and v[c]

median_of_medians 🔒 Experimental

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 🔒 Experimental

min_index 🔒 Experimental

Helper function that returns the index of the minimum element in the slice using the given comparator function

ninther 🔒 Experimental

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 🔒 Experimental

Reorders the slice such that the element at index is at its final sorted position.

partition_at_index_loop 🔒 Experimental