Module core::slice::select

Slice selection

This module contains the implementation for slice::select_nth_unstable. It uses an introselect algorithm based on Orson Peters’ pattern-defeating quicksort, published at: https://github.com/orlp/pdqsort

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

• MAX_INSERTION 🔒

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] and v[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
  Reorder the slice such that the element at index is at its final sorted position.
• partition_at_index_loop 🔒