Function core::slice::sort::merge_sort

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)

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:

1. for every i in 1..runs.len(): runs[i - 1].len > runs[i].len
2. for every i in 2..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.