Module pivot

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

This module contains the logic for pivot selection.

Constants

PSEUDO_MEDIAN_REC_THRESHOLD 🔒 Experimental

Functions

choose_pivotExperimental

Selects a pivot from v. Algorithm taken from glidesort by Orson Peters.

median3 🔒 Experimental

Calculates the median of 3 elements.

median3_rec 🔒 ^⚠Experimental

Calculates an approximate median of 3 elements from sections a, b, c, or recursively from an approximation of each, if they’re large enough. By dividing the size of each section by 8 when recursing we have logarithmic recursion depth and overall sample from f(n) = 3*f(n/8) -> f(n) = O(n^(log(3)/log(8))) ~= O(n^0.528) elements.