Function 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
)
🔬This is a nightly-only experimental API. (
slice_internals
)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.