Function kvarn::prelude::utils::prelude::compact_str::core::slice::sort::merge_sort
source · pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>(
v: &mut [T],
is_less: &mut CmpF,
elem_alloc_fn: ElemAllocF,
elem_dealloc_fn: ElemDeallocF,
run_alloc_fn: RunAllocF,
run_dealloc_fn: RunDeallocF
)where
CmpF: FnMut(&T, &T) -> bool,
ElemAllocF: Fn(usize) -> *mut T,
ElemDeallocF: Fn(*mut T, usize),
RunAllocF: Fn(usize) -> *mut TimSortRun,
RunDeallocF: Fn(*mut TimSortRun, usize),
🔬This is a nightly-only experimental API. (
slice_internals
)Available on non-crate feature
miri-test-libstd
only.Expand description
This merge sort borrows some (but not all) ideas from TimSort, which used to be described in detail here. However Python has switched to a Powersort based implementation.
The algorithm identifies strictly descending and non-descending subsequences, which are called natural runs. There is a stack of pending runs yet to be merged. Each newly found run is pushed onto the stack, and then some pairs of adjacent runs are merged until these two invariants are satisfied:
- for every
i
in1..runs.len()
:runs[i - 1].len > runs[i].len
- for every
i
in2..runs.len()
:runs[i - 2].len > runs[i - 1].len + runs[i].len
The invariants ensure that the total running time is O(n * log(n)) worst-case.