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)

这个归并排序借用了一些 (但不是全部) 来自 TimSort 的想法，它曾经被详细描述在 这里。 但是 Python 已经切换到基于 Powersort 的实现。

该算法识别严格降序和非降序的子序列，这些子序列称为自然行程。有待合并的待处理运行栈。 将每个新发现的运行推入栈中，然后合并一些相邻的运行对，直到这两个不变量得到满足：

1. 对于 1..runs.len() 中的每个 i: runs[i - 1].len > runs[i].len
2. 对于 2..runs.len() 中的每个 i: runs[i - 2].len > runs[i - 1].len + runs[i].len

不变量确保最坏情况下的总运行时间为 O(n*log(* n*))。