Module `drift`

This module contains the hybrid top-level loop combining bottom-up Mergesort with top-down Quicksort.

Structs

DriftsortRun Compactly stores the length of a run, and whether or not it is sorted. This can always fit in a usize because the maximum slice length is isize::MAX.

create_run Creates a new logical run.
logical_merge
merge_tree_depth
merge_tree_scale_factor
sort Sorts v based on comparison function is_less. If eager_sort is true, it will only do small-sorts and physical merges, ensuring O(N * log(N)) worst-case complexity. scratch.len() must be at least max(v.len() - v.len() / 2, SMALL_SORT_GENERAL_SCRATCH_LEN) otherwise the implementation may abort. Fully ascending and descending inputs will be sorted with exactly N - 1 comparisons.
sqrt_approx
stable_quicksort