//! 切片分类
//!
//! 该模块包含基于 Orson Peters 的模式失败快速排序的排序算法，发布于: <https://github.com/orlp/pdqsort>
//!
//!
//! 不稳定排序与核心兼容，因为它不分配内存，这与我们的稳定排序实现不同。
//!
//! 此外还包含了 `slice::sort` 基于 TimSort 使用的稳定排序的核心逻辑。
//!
//!

use crate::cmp;
use crate::mem::{self, MaybeUninit, SizedTypeProperties};
use crate::ptr;

// 丢弃时，从 `src` 复制到 `dest`。
struct InsertionHole<T> {
    src: *const T,
    dest: *mut T,
}

impl<T> Drop for InsertionHole<T> {
    fn drop(&mut self) {
        // SAFETY: 这是一个帮助程序类。请参考其用法以确保正确性。
        // 即，必须确保 `src` 和 `dst` 没有按照 `ptr::copy_nonoverlapping` 的要求重叠并且都对写入有效。
        //
        unsafe {
            ptr::copy_nonoverlapping(self.src, self.dest, 1);
        }
    }
}

/// 将 `v[v.len() - 1]` 插入到预排序序列 `v[..v.len() - 1]` 中，以便整个 `v[..]` 都已排序。
///
unsafe fn insert_tail<T, F>(v: &mut [T], is_less: &mut F)
where
    F: FnMut(&T, &T) -> bool,
{
    debug_assert!(v.len() >= 2);

    let arr_ptr = v.as_mut_ptr();
    let i = v.len() - 1;

    // SAFETY: 调用者必须确保 v 至少为 len 2.
    unsafe {
        // 请参见 insert_head，其中讨论了为什么这种方法是有益的。
        let i_ptr = arr_ptr.add(i);

        // 我们在这里使用 i_ptr 很重要。
        // 如果此检查是肯定的并且我们继续，我们要确保 is_less 没有看到该值的其他副本。
        // 否则我们将不得不将其复制回去。
        if is_less(&*i_ptr, &*i_ptr.sub(1)) {
            // 重要的是，我们从现在开始使用 tmp 进行比较。
            // 因为它是将被复制回的值。
            // 从理论上讲，如果我们复制回错误的值，我们可能会产生分歧。
            let tmp = mem::ManuallyDrop::new(ptr::read(i_ptr));
            // `hole` 始终跟踪插入过程的中间状态，这有两个目的：
            // 1. 从 `is_less` 中的 panics 保护 `v` 的完整性。
            // 2. 最后将 `v` 中剩余的 hole 填充。
            //
            // Panic 安全：
            //
            // 如果在此过程中的任何时候 `is_less` panics，`hole` 都会被丢弃，并用 `tmp` 填充 `v` 中的 hole，从而确保 `v` 仍将其最初持有的每个对象精确地保留一次。
            //
            //
            //
            let mut hole = InsertionHole { src: &*tmp, dest: i_ptr.sub(1) };
            ptr::copy_nonoverlapping(hole.dest, i_ptr, 1);

            // SAFETY: 我们知道我至少 1.
            for j in (0..(i - 1)).rev() {
                let j_ptr = arr_ptr.add(j);
                if !is_less(&*tmp, &*j_ptr) {
                    break;
                }

                ptr::copy_nonoverlapping(j_ptr, hole.dest, 1);
                hole.dest = j_ptr;
            }
            // `hole` 被丢弃，因此将 `tmp` 复制到 `v` 中剩余的 hole 中。
        }
    }
}

/// 将 `v[0]` 插入到预排序序列 `v[1..]` 中，以便整个 `v[..]` 都被排序。
///
/// 这是插入排序的必不可少的子例程。
unsafe fn insert_head<T, F>(v: &mut [T], is_less: &mut F)
where
    F: FnMut(&T, &T) -> bool,
{
    debug_assert!(v.len() >= 2);

    // SAFETY: 调用者必须确保 v 至少为 len 2.
    unsafe {
        if is_less(v.get_unchecked(1), v.get_unchecked(0)) {
            let arr_ptr = v.as_mut_ptr();

            // 这里有三种实现插入的方法：
            //
            // 1. 交换相邻的元素，直到第一个到达其最终目的地。
            //    但是，这样一来，我们就可以复制不必要的数据。
            //    如果元素是大型结构 (复制成本很高)，则此方法的速度会很慢。
            //
            // 2. 迭代直到找到第一个元素的正确位置。
            // 然后，移动后继的元素为其腾出空间，最后将其放入剩余的 hole 中。
            // 这是一个好方法。
            //
            // 3. 将第一个元素复制到一个临时变量中。迭代直到找到正确的位置。
            // 在继续操作时，将每个遍历的元素复制到它前面的插槽中。
            // 最后，将数据从临时变量复制到剩余的 hole 中。
            // 这个方法很好。
            // 基准测试显示出比第二种方法更好的性能。
            //
            // 所有方法均进行了基准测试，第 3 种方法显示最佳结果。因此，我们选择了那个。
            let tmp = mem::ManuallyDrop::new(ptr::read(arr_ptr));

            // `hole` 始终跟踪插入过程的中间状态，这有两个目的：
            // 1. 从 `is_less` 中的 panics 保护 `v` 的完整性。
            // 2. 最后将 `v` 中剩余的 hole 填充。
            //
            // Panic 安全：
            //
            // 如果在此过程中的任何时候 `is_less` panics，`hole` 都会被丢弃，并用 `tmp` 填充 `v` 中的 hole，从而确保 `v` 仍将其最初持有的每个对象精确地保留一次。
            //
            //
            //
            let mut hole = InsertionHole { src: &*tmp, dest: arr_ptr.add(1) };
            ptr::copy_nonoverlapping(arr_ptr.add(1), arr_ptr.add(0), 1);

            for i in 2..v.len() {
                if !is_less(&v.get_unchecked(i), &*tmp) {
                    break;
                }
                ptr::copy_nonoverlapping(arr_ptr.add(i), arr_ptr.add(i - 1), 1);
                hole.dest = arr_ptr.add(i);
            }
            // `hole` 被丢弃，因此将 `tmp` 复制到 `v` 中剩余的 hole 中。
        }
    }
}

/// 假设 `v[..offset]` 已经排序，则对 `v` 进行排序。
///
/// 切勿内联此函数以避免代码膨胀。它仍然可以很好地优化并且几乎没有性能影响。
/// 在某些情况下甚至可以提高性能。
#[inline(never)]
pub(super) fn insertion_sort_shift_left<T, F>(v: &mut [T], offset: usize, is_less: &mut F)
where
    F: FnMut(&T, &T) -> bool,
{
    let len = v.len();

    // 此处使用断言可提高性能。
    assert!(offset != 0 && offset <= len);

    // 将未排序区域 v [i..] 的每个元素尽可能向左移动以使 v 排序。
    for i in offset..len {
        // SAFETY: 我们测试了 `offset` 必须至少为 1，所以只有在 len >= 时才进入这个循环 2.
        // 范围是排他的，我们知道 `i` 必须至少为 1，所以这个切片至少有 > least 2.
        //
        unsafe {
            insert_tail(&mut v[..=i], is_less);
        }
    }
}

/// 假设 `v[offset..]` 已经排序，则对 `v` 进行排序。
///
/// 切勿内联此函数以避免代码膨胀。它仍然可以很好地优化并且几乎没有性能影响。
/// 在某些情况下甚至可以提高性能。
#[inline(never)]
fn insertion_sort_shift_right<T, F>(v: &mut [T], offset: usize, is_less: &mut F)
where
    F: FnMut(&T, &T) -> bool,
{
    let len = v.len();

    // 此处使用断言可提高性能。
    assert!(offset != 0 && offset <= len && len >= 2);

    // 将未排序区域 v [..i] 的每个元素尽可能向左移动以使 v 排序。
    for i in (0..offset).rev() {
        // SAFETY: 我们测试过 `offset` 必须至少为 1，因此只有在 len >= 2.We 确保切片长度始终至少为 2 时才进入此循环。
        // 我们知道 start_found 至少会比 end 少一位，并且范围是独占的。
        // 这给了我们我总是 <= (end-2)。
        //
        unsafe {
            insert_head(&mut v[i..len], is_less);
        }
    }
}

/// 通过移动几个乱序的元素来对切片进行部分排序。
///
/// 如果切片末尾排序，则返回 `true`。该函数是 *O*(*n*) 最坏的情况。
#[cold]
fn partial_insertion_sort<T, F>(v: &mut [T], is_less: &mut F) -> bool
where
    F: FnMut(&T, &T) -> bool,
{
    // 将移位的相邻无序对的最大数量。
    const MAX_STEPS: usize = 5;
    // 如果切片短于此，请勿移动任何元素。
    const SHORTEST_SHIFTING: usize = 50;

    let len = v.len();
    let mut i = 1;

    for _ in 0..MAX_STEPS {
        // SAFETY: 我们已经用 `i < len` 明确地进行了边界检查。
        // 我们所有的后续索引仅在 `0 <= index < len` 范围内
        unsafe {
            // 查找下一对相邻的乱序元素。
            while i < len && !is_less(v.get_unchecked(i), v.get_unchecked(i - 1)) {
                i += 1;
            }
        }

        // 我们完成了吗？
        if i == len {
            return true;
        }

        // 不要在短数组上移动元素，这会降低性能。
        if len < SHORTEST_SHIFTING {
            return false;
        }

        // 交换找到的一对元素。这使它们处于正确的顺序。
        v.swap(i - 1, i);

        if i >= 2 {
            // 将较小的元素向左移动。
            insertion_sort_shift_left(&mut v[..i], i - 1, is_less);

            // 将较大的元素向右移动。
            insertion_sort_shift_right(&mut v[..i], 1, is_less);
        }
    }

    // 未能在有限的步骤中对切片进行排序。
    false
}

/// 使用堆排序对 `v` 进行排序，这保证了 *O*(*n*\*log(* n*)) 最坏的情况。
#[cold]
#[unstable(feature = "sort_internals", reason = "internal to sort module", issue = "none")]
pub fn heapsort<T, F>(v: &mut [T], mut is_less: F)
where
    F: FnMut(&T, &T) -> bool,
{
    // 该二进制堆遵守不变量 `parent >= child`。
    let mut sift_down = |v: &mut [T], mut node| {
        loop {
            // `node` 的子节点。
            let mut child = 2 * node + 1;
            if child >= v.len() {
                break;
            }

            // 选择更大的子节点。
            if child + 1 < v.len() {
                // 我们需要一个分支来确保索引不会越界，但它是高度可预测的。
                //
                // 然而，比较最好是无分支的，特别是对于，原语。
                child += is_less(&v[child], &v[child + 1]) as usize;
            }

            // 如果不变量位于 `node`，则停止。
            if !is_less(&v[node], &v[child]) {
                break;
            }

            // 与更大的子节点交换 `node`，向下移动一步，然后继续筛分。
            v.swap(node, child);
            node = child;
        }
    };

    // 在线性时间内构建堆。
    for i in (0..v.len() / 2).rev() {
        sift_down(v, i);
    }

    // 从堆中弹出最大元素。
    for i in (1..v.len()).rev() {
        v.swap(0, i);
        sift_down(&mut v[..i], 0);
    }
}

/// 将 `v` 划分为小于 `pivot` 的元素，然后划分为大于或等于 `pivot` 的元素。
///
///
/// 返回小于 `pivot` 的元素数。
///
/// 为了最小化分支操作的成本，逐块执行分区。
/// [块快速排序][pdf] 论文中提出了这个想法。
///
/// [pdf]: https://drops.dagstuhl.de/opus/volltexte/2016/6389/pdf/LIPIcs-ESA-2016-38.pdf
fn partition_in_blocks<T, F>(v: &mut [T], pivot: &T, is_less: &mut F) -> usize
where
    F: FnMut(&T, &T) -> bool,
{
    // 典型块中的元素数。
    const BLOCK: usize = 128;

    // 分区算法重复以下步骤，直到完成：
    //
    // 1. 从左侧跟踪一个块，以识别大于或等于枢轴的元素。
    // 2. 从右侧跟踪一个块，以识别小于枢轴的元素。
    // 3. 在左侧和右侧之间交换已标识的元素。
    //
    // 我们为元素块保留以下变量：
    //
    // 1. `block` - 块中的元素数。
    // 2. `start` - 指向 `offsets` 数组的起始指针。
    // 3. `end` - 指向 `offsets` 数组的结束指针。
    // 4. `offsets` - 块内乱序元素的索引。

    // 左侧的当前块 (从 `l` 到 `l.add(block_l)`)。
    let mut l = v.as_mut_ptr();
    let mut block_l = BLOCK;
    let mut start_l = ptr::null_mut();
    let mut end_l = ptr::null_mut();
    let mut offsets_l = [MaybeUninit::<u8>::uninit(); BLOCK];

    // 右侧的当前块 (从 `r.sub(block_r)` 到 `r`)。
    // SAFETY: .add() 的文档特别提到 `vec.as_ptr().add(vec.len())` 总是安全的
    let mut r = unsafe { l.add(v.len()) };
    let mut block_r = BLOCK;
    let mut start_r = ptr::null_mut();
    let mut end_r = ptr::null_mut();
    let mut offsets_r = [MaybeUninit::<u8>::uninit(); BLOCK];

    // FIXME: 当我们得到 VLA 时，请尝试创建一个长度为 `min(v.len(), 2 * BLOCK)` 的数组，而不是两个长度为 `BLOCK` 的固定大小的数组。
    // VLA 可能会提高缓存效率。

    // 返回指针 `l` (inclusive) 和 `r` (exclusive) 之间的元素数。
    fn width<T>(l: *mut T, r: *mut T) -> usize {
        assert!(mem::size_of::<T>() > 0);
        // FIXME: 这应该可能使用 `offset_from`，但需要进行更多调查 (包括在 miri 中运行测试)。
        //
        (r.addr() - l.addr()) / mem::size_of::<T>()
    }

    loop {
        // 当 `l` 和 `r` 非常接近时，我们将逐块进行分区。
        // 然后，我们进行一些修补工作，以便在其余元素之间进行划分。
        let is_done = width(l, r) <= 2 * BLOCK;

        if is_done {
            // 剩余元素数 (仍未与枢轴进行比较)。
            let mut rem = width(l, r);
            if start_l < end_l || start_r < end_r {
                rem -= BLOCK;
            }

            // 调整块大小，以使左右块不重叠，但要完全对齐以覆盖整个剩余间隙。
            //
            if start_l < end_l {
                block_r = rem;
            } else if start_r < end_r {
                block_l = rem;
            } else {
                // 在上次迭代期间要在两个块上切换的元素数量相同，因此任何一个块上都没有剩余的元素。
                // 用大致相同大小的块覆盖剩余的项。
                //
                block_l = rem / 2;
                block_r = rem - block_l;
            }
            debug_assert!(block_l <= BLOCK && block_r <= BLOCK);
            debug_assert!(width(l, r) == block_l + block_r);
        }

        if start_l == end_l {
            // 从左侧跟踪 `block_l` 元素。
            start_l = MaybeUninit::slice_as_mut_ptr(&mut offsets_l);
            end_l = start_l;
            let mut elem = l;

            for i in 0..block_l {
                // SAFETY: 以下不安全操作涉及 `offset` 的使用。
                //         根据函数所需的条件，我们满足它们，因为：
                //         1. `offsets_l` 是栈分配的，因此被视为单独分配的对象。
                //         2. 函数 `is_less` 返回 `bool`。
                //            转换 `bool` 不会使 `isize` 溢出。
                //         3. 我们保证 `block_l` 将是 `<= BLOCK`。
                //            另外，`end_l` 最初设置为在栈上声明的 `offsets_` 的开始指针。
                //            因此，我们知道即使在最坏的情况下 (`is_less` 的所有调用都返回 false)，我们最多只能有 1 个字节通过结尾。
                //        这里的另一个不安全操作是解引用 `elem`。
                //        但是，`elem` 最初是指向切片的 begin 指针，始终有效。
                unsafe {
                    // 无分支比较。
                    *end_l = i as u8;
                    end_l = end_l.add(!is_less(&*elem, pivot) as usize);
                    elem = elem.add(1);
                }
            }
        }

        if start_r == end_r {
            // 从右侧跟踪 `block_r` 元素。
            start_r = MaybeUninit::slice_as_mut_ptr(&mut offsets_r);
            end_r = start_r;
            let mut elem = r;

            for i in 0..block_r {
                // SAFETY: 以下不安全操作涉及 `offset` 的使用。
                //         根据函数所需的条件，我们满足它们，因为：
                //         1. `offsets_r` 是栈分配的，因此被视为单独分配的对象。
                //         2. 函数 `is_less` 返回 `bool`。
                //            转换 `bool` 不会使 `isize` 溢出。
                //         3. 我们保证 `block_r` 将是 `<= BLOCK`。
                //            另外，`end_r` 最初设置为在栈上声明的 `offsets_` 的开始指针。
                //            因此，我们知道即使在最坏的情况下 (`is_less` 的所有调用都返回 true)，我们最多只能将 1 个字节传递到末尾。
                //        这里的另一个不安全操作是解引用 `elem`。
                //        但是，`elem` 最初是末尾的 `1 *sizeof(T)`，在访问它之前，我们先将其递减 `1* sizeof(T)`。
                //        另外，断言 `block_r` 小于 `BLOCK`，因此 `elem` 至多将指向切片的开头。
                unsafe {
                    // 无分支比较。
                    elem = elem.sub(1);
                    *end_r = i as u8;
                    end_r = end_r.add(is_less(&*elem, pivot) as usize);
                }
            }
        }

        // 要在左侧和右侧之间交换的乱序元素的数量。
        let count = cmp::min(width(start_l, end_l), width(start_r, end_r));

        if count > 0 {
            macro_rules! left {
                () => {
                    l.add(usize::from(*start_l))
                };
            }
            macro_rules! right {
                () => {
                    r.sub(usize::from(*start_r) + 1)
                };
            }

            // 与一次交换一对相比，执行循环置换更为有效。
            // 这并不严格等同于交换，但是使用较少的内存操作即可产生类似的结果。
            //

            // SAFETY: `ptr::read` 的使用是有效的，因为在 `offsets_l` 和 `offsets_r` 中至少有一个元素，所以 `left!` 是一个有效的读取指针。
            //
            // `left!` 的使用涉及在 `l` 上调用 `offset`，它指向 `v` 的开头。`start_l` 指向的所有偏移量最多为 `block_l`，因此这些 `offset` 调用是安全的，因为所有读取都在块内。相同的参数也适用于 `right!` 的用法。
            //
            // 对 `start_l.offset` 的调用是有效的，因为它们最多有 `count-1` 个，加上不安全块末尾的最后一个，其中 `count` 是 `offsets_l` 和 `offsets_r` 中收集的最小偏移量，因此不存在不存在的风险足够的元素。
            // 同样的推理适用于对 `start_r.offset` 的调用。
            //
            // 对 `copy_nonoverlapping` 的调用是安全的，因为 `left!` 和 `right!` 保证不重叠，并且由于上述推理是有效的。
            //
            //
            //
            //
            //
            //
            //
            unsafe {
                let tmp = ptr::read(left!());
                ptr::copy_nonoverlapping(right!(), left!(), 1);

                for _ in 1..count {
                    start_l = start_l.add(1);
                    ptr::copy_nonoverlapping(left!(), right!(), 1);
                    start_r = start_r.add(1);
                    ptr::copy_nonoverlapping(right!(), left!(), 1);
                }

                ptr::copy_nonoverlapping(&tmp, right!(), 1);
                mem::forget(tmp);
                start_l = start_l.add(1);
                start_r = start_r.add(1);
            }
        }

        if start_l == end_l {
            // 左侧块中的所有乱序元素均已移动。移至下一个块。

            // block-width-guarantee
            // SAFETY: 如果 `!is_done` 那么至少保证宽度为 `2*BLOCK` 宽。由于 `offsets_l` 的大小，`offsets_l` 中最多有 `BLOCK` 个元素，所以 `offset` 操作是安全的。
            // 否则，`is_done` 情况下的调试断言保证 `width(l, r) == block_l + block_r`，即块大小已被调整以考虑较少数量的剩余元素。
            //
            //
            //
            l = unsafe { l.add(block_l) };
        }

        if start_r == end_r {
            // 右侧块中的所有乱序元素均已移动。移至上一个块。

            // SAFETY: 与 [block-width-guarantee] 的参数相同。
            // 这是一个完整的 `2*BLOCK` 块，或者 `block_r` 已针对最后少数元素进行了调整。
            r = unsafe { r.sub(block_r) };
        }

        if is_done {
            break;
        }
    }

    // 现在剩下的全部是至多一个块 (左侧或右侧)，其中需要移动的乱序元素。
    // 这些剩余的元素可以简单地移到其块内的末尾。
    //

    if start_l < end_l {
        // 剩下的方块仍然保留。
        // 将其剩余的乱序元素移到最右边。
        debug_assert_eq!(width(l, r), block_l);
        while start_l < end_l {
            // remaining-elements-safety
            // SAFETY: 当循环条件成立时 `offsets_l` 中仍有元素，因此将 `end_l` 指向前一个元素是安全的。
            //
            // 如果 `ptr::swap` 的参数对读和写都有效，则它是安全的：
            //  - 根据上面的调试断言，`l` 和 `r` 之间的距离是 `block_l` 元素，因此 `start_l` 和 `end_l` 之间最多可以有 `block_l` 剩余偏移量。
            //  这意味着 `r` 最多将向后移动 `block_l` 步，这使得 `r.offset` 调用有效 (在那个时候 `l == r`)。
            //  - `offsets_l` 包含在最后一个块的分区期间收集到的 `v` 的有效偏移量，因此 `l.offset` 调用是有效的。
            //
            //
            //
            //
            unsafe {
                end_l = end_l.sub(1);
                ptr::swap(l.add(usize::from(*end_l)), r.sub(1));
                r = r.sub(1);
            }
        }
        width(v.as_mut_ptr(), r)
    } else if start_r < end_r {
        // 右边的块仍然存在。
        // 将其剩余的乱序元素移到最左边。
        debug_assert_eq!(width(l, r), block_r);
        while start_r < end_r {
            // SAFETY: 请参见 [剩余元素安全][remaining-elements-safety] 中的推理。
            unsafe {
                end_r = end_r.sub(1);
                ptr::swap(l, r.sub(usize::from(*end_r) + 1));
                l = l.add(1);
            }
        }
        width(v.as_mut_ptr(), l)
    } else {
        // 没什么可做的，我们已经完成。
        width(v.as_mut_ptr(), l)
    }
}

/// 将 `v` 划分为小于 `v[pivot]` 的元素，然后划分为大于或等于 `v[pivot]` 的元素。
///
///
/// 返回一个元组：
///
/// 1. 小于 `v[pivot]` 的元素数。
/// 2. 如果 `v` 已经分区，则为 True。
pub(super) fn partition<T, F>(v: &mut [T], pivot: usize, is_less: &mut F) -> (usize, bool)
where
    F: FnMut(&T, &T) -> bool,
{
    let (mid, was_partitioned) = {
        // 将枢轴放置在切片的开头。
        v.swap(0, pivot);
        let (pivot, v) = v.split_at_mut(1);
        let pivot = &mut pivot[0];

        // 将枢轴读取到栈分配的变量中以提高效率。
        // 如果执行以下比较操作 panics，则枢轴将自动写回到切片中。

        // SAFETY: `pivot` 是对 `v` 第一个元素的引用，所以 `ptr::read` 是安全的。
        let tmp = mem::ManuallyDrop::new(unsafe { ptr::read(pivot) });
        let _pivot_guard = InsertionHole { src: &*tmp, dest: pivot };
        let pivot = &*tmp;

        // 查找第一对乱序元素。
        let mut l = 0;
        let mut r = v.len();

        // SAFETY: 下面的不安全性涉及对数组进行索引。
        // 对于第一个：我们已经在这里使用 `l < r` 进行了边界检查。
        // 对于第二个：我们最初有 `l == 0` 和 `r == v.len()`，我们在每次索引操作中都检查了 `l < r`。
        //                     从这里我们知道 `r` 必须至少是 `r == l`，这从第一个开始就被证明是有效的。
        unsafe {
            // 找到大于或等于枢轴的第一个元素。
            while l < r && is_less(v.get_unchecked(l), pivot) {
                l += 1;
            }

            // 找到比枢轴更小的最后一个元素。
            while l < r && !is_less(v.get_unchecked(r - 1), pivot) {
                r -= 1;
            }
        }

        (l + partition_in_blocks(&mut v[l..r], pivot, is_less), l >= r)

        // `_pivot_guard` 离开作用域并将 pivot (这是一个栈分配的变量) 写回到它原来所在的切片中。
        // 这一步对于确保安全至关重要！
        //
    };

    // 将枢轴放置在两个分区之间。
    v.swap(0, mid);

    (mid, was_partitioned)
}

/// 将 `v` 划分为等于 `v[pivot]` 的元素，后跟大于 `v[pivot]` 的元素。
///
/// 返回等于枢轴的元素数。
/// 假定 `v` 不包含小于枢轴的元素。
pub(super) fn partition_equal<T, F>(v: &mut [T], pivot: usize, is_less: &mut F) -> usize
where
    F: FnMut(&T, &T) -> bool,
{
    // 将枢轴放置在切片的开头。
    v.swap(0, pivot);
    let (pivot, v) = v.split_at_mut(1);
    let pivot = &mut pivot[0];

    // 将枢轴读取到栈分配的变量中以提高效率。
    // 如果执行以下比较操作 panics，则枢轴将自动写回到切片中。
    // SAFETY: 此处的指针是有效的，因为它是从引用到切片获得的。
    let tmp = mem::ManuallyDrop::new(unsafe { ptr::read(pivot) });
    let _pivot_guard = InsertionHole { src: &*tmp, dest: pivot };
    let pivot = &*tmp;

    // 现在对切片进行分区。
    let mut l = 0;
    let mut r = v.len();
    loop {
        // SAFETY: 下面的不安全性涉及对数组进行索引。
        // 对于第一个：我们已经在这里使用 `l < r` 进行了边界检查。
        // 对于第二个：我们最初有 `l == 0` 和 `r == v.len()`，我们在每次索引操作中都检查了 `l < r`。
        //                     从这里我们知道 `r` 必须至少是 `r == l`，这从第一个开始就被证明是有效的。
        unsafe {
            // 找到第一个大于枢轴的元素。
            while l < r && !is_less(pivot, v.get_unchecked(l)) {
                l += 1;
            }

            // 找到等于枢轴的最后一个元素。
            while l < r && is_less(pivot, v.get_unchecked(r - 1)) {
                r -= 1;
            }

            // 我们完成了吗？
            if l >= r {
                break;
            }

            // 交换找到的一对乱序元素。
            r -= 1;
            let ptr = v.as_mut_ptr();
            ptr::swap(ptr.add(l), ptr.add(r));
            l += 1;
        }
    }

    // 我们发现 `l` 元素等于 pivot。为 pivot 本身加 1。
    l + 1

    // `_pivot_guard` 离开作用域并将 pivot (这是一个栈分配的变量) 写回到它原来所在的切片中。
    // 这一步对于确保安全至关重要！
}

/// 散布一些元素，以尝试破坏可能导致快速排序中的分区不平衡的模式。
///
#[cold]
pub(super) fn break_patterns<T>(v: &mut [T]) {
    let len = v.len();
    if len >= 8 {
        let mut seed = len;
        let mut gen_usize = || {
            // George Marsaglia 撰写的 "Xorshift RNGs" 论文中的伪随机数生成器。
            if usize::BITS <= 32 {
                let mut r = seed as u32;
                r ^= r << 13;
                r ^= r >> 17;
                r ^= r << 5;
                seed = r as usize;
                seed
            } else {
                let mut r = seed as u64;
                r ^= r << 13;
                r ^= r >> 7;
                r ^= r << 17;
                seed = r as usize;
                seed
            }
        };

        // 取该数字取模的随机数。
        // 该数字适合 `usize`，因为 `len` 不大于 `isize::MAX`。
        let modulus = len.next_power_of_two();

        // 一些关键候选人将在该指数附近。让我们随机化它们。
        let pos = len / 4 * 2;

        for i in 0..3 {
            // 生成一个以 `len` 为模的随机数。
            // 但是，为了避免昂贵的操作，我们首先将其取模为 2 的幂，然后减小 `len` 直到它适合 `[0, len - 1]` 范围。
            //
            let mut other = gen_usize() & (modulus - 1);

            // `other` 保证小于 `2 * len`。
            if other >= len {
                other -= len;
            }

            v.swap(pos - 1 + i, other);
        }
    }
}

/// 在 `v` 中选择一个枢轴，如果切片可能已经排序，则返回索引和 `true`。
///
/// `v` 中的元素可能会在此过程中重新排序。
pub(super) fn choose_pivot<T, F>(v: &mut [T], is_less: &mut F) -> (usize, bool)
where
    F: FnMut(&T, &T) -> bool,
{
    // 选择中位数中位数方法的最小长度。
    // 较短的切片使用简单的三位数中位数方法。
    const SHORTEST_MEDIAN_OF_MEDIANS: usize = 50;
    // 在此函数中可以执行的最大交换次数。
    const MAX_SWAPS: usize = 4 * 3;

    let len = v.len();

    // 我们将在附近选择一个枢轴的三个指数。
    let mut a = len / 4 * 1;
    let mut b = len / 4 * 2;
    let mut c = len / 4 * 3;

    // 计算在对索引进行排序时我们将要执行的交换总数。
    let mut swaps = 0;

    if len >= 8 {
        // 交换索引，以便 `v[a] <= v[b]`。
        // SAFETY: `len >= 8` 所以在 `a`、`b` 和 `c` 的邻域中至少有两个元素。
        // 这意味着对 `sort_adjacent` 的三个调用导致对 `sort3` 的相应调用以及每个指针周围的有效 3 项邻域，这反过来意味着对 `sort2` 的调用是通过有效的引用完成的。
        //
        // 因此 `v.get_unchecked` 调用是安全的，`ptr::swap` 调用也是安全的。
        //
        //
        let mut sort2 = |a: &mut usize, b: &mut usize| unsafe {
            if is_less(v.get_unchecked(*b), v.get_unchecked(*a)) {
                ptr::swap(a, b);
                swaps += 1;
            }
        };

        // 交换索引，以便 `v[a] <= v[b] <= v[c]`。
        let mut sort3 = |a: &mut usize, b: &mut usize, c: &mut usize| {
            sort2(a, b);
            sort2(b, c);
            sort2(a, b);
        };

        if len >= SHORTEST_MEDIAN_OF_MEDIANS {
            // 查找 `v[a - 1], v[a], v[a + 1]` 的中位数，并将索引存储到 `a` 中。
            let mut sort_adjacent = |a: &mut usize| {
                let tmp = *a;
                sort3(&mut (tmp - 1), a, &mut (tmp + 1));
            };

            // 查找 `a`，`b` 和 `c` 附近的中位数。
            sort_adjacent(&mut a);
            sort_adjacent(&mut b);
            sort_adjacent(&mut c);
        }

        // 在 `a`，`b` 和 `c` 中找到中位数。
        sort3(&mut a, &mut b, &mut c);
    }

    if swaps < MAX_SWAPS {
        (b, swaps == 0)
    } else {
        // 已执行最大交换次数。
        // 切片可能是降序的，或者大多是降序的，因此反转可能有助于更快地对其进行排序。
        v.reverse();
        (len - 1 - b, true)
    }
}

/// 递归排序 `v`。
///
/// 如果切片在原始数组中具有前身，则将其指定为 `pred`。
///
/// `limit` 是切换到 `heapsort` 之前允许的不平衡分区数。
/// 如果为零，则此函数将立即切换到 heapsort。
fn recurse<'a, T, F>(mut v: &'a mut [T], is_less: &mut F, mut pred: Option<&'a T>, mut limit: u32)
where
    F: FnMut(&T, &T) -> bool,
{
    // 长度不超过此长度的切片将使用插入排序进行排序。
    const MAX_INSERTION: usize = 20;

    // 如果最后一个分区合理平衡，则为 true。
    let mut was_balanced = true;
    // 如果最后一个分区没有重排元素 (切片已分区)，则为 true。
    let mut was_partitioned = true;

    loop {
        let len = v.len();

        // 非常短的切片使用插入排序进行排序。
        if len <= MAX_INSERTION {
            if len >= 2 {
                insertion_sort_shift_left(v, 1, is_less);
            }
            return;
        }

        // 如果做出了太多错误的枢轴选择，则只需回退到 heapsort 以确保 `O(n * log(n))` 最坏的情况。
        //
        if limit == 0 {
            heapsort(v, is_less);
            return;
        }

        // 如果最后一个分区不平衡，请尝试通过改组一些元素来破坏切片中的模式。
        // 希望这次我们选择一个更好的支点。
        if !was_balanced {
            break_patterns(v);
            limit -= 1;
        }

        // 选择一个枢轴，然后尝试猜测切片是否已排序。
        let (pivot, likely_sorted) = choose_pivot(v, is_less);

        // 如果最后一个分区是平衡的并且没有打乱元素，并且如果 pivot 选择预测切片可能已经排序...
        //
        if was_balanced && was_partitioned && likely_sorted {
            // 尝试识别几个乱序的元素，然后将它们移到正确的位置。
            // 如果切片最终被完全排序，那么我们就完成了。
            if partial_insertion_sort(v, is_less) {
                return;
            }
        }

        // 如果选择的枢轴等于前一个枢轴，则它是切片中的最小元素。
        // 将切片划分为等于和大于枢轴的元素。
        // 当切片包含许多重复元素时，通常会遇到这种情况。
        if let Some(p) = pred {
            if !is_less(p, &v[pivot]) {
                let mid = partition_equal(v, pivot, is_less);

                // 继续对大于枢轴的元素进行排序。
                v = &mut v[mid..];
                continue;
            }
        }

        // 对切片进行分区。
        let (mid, was_p) = partition(v, pivot, is_less);
        was_balanced = cmp::min(mid, len - mid) >= len / 8;
        was_partitioned = was_p;

        // 将切片分为 `left`，`pivot` 和 `right`。
        let (left, right) = v.split_at_mut(mid);
        let (pivot, right) = right.split_at_mut(1);
        let pivot = &pivot[0];

        // 递归到较短的一侧只是为了最大程度地减少递归调用的总数并占用较少的栈空间。
        // 然后，继续较长的那一面 (这类似于尾部递归)。
        //
        if left.len() < right.len() {
            recurse(left, is_less, pred, limit);
            v = right;
            pred = Some(pivot);
        } else {
            recurse(right, is_less, Some(pivot), limit);
            v = left;
        }
    }
}

/// 使用模式破坏快速排序对 `v` 进行排序，这是 *O*(*n*\*log(* n*)) 最坏的情况。
pub fn quicksort<T, F>(v: &mut [T], mut is_less: F)
where
    F: FnMut(&T, &T) -> bool,
{
    // 零大小类型的排序没有有意义的行为。
    if T::IS_ZST {
        return;
    }

    // 将不平衡分区的数量限制为 `floor(log2(len)) + 1`。
    let limit = usize::BITS - v.len().leading_zeros();

    recurse(v, &mut is_less, None, limit);
}

/// 使用 `buf` 作为临时存储合并非递减运行 `v[..mid]` 和 `v[mid..]`，并将结果存储到 `v[..]` 中。
///
/// # Safety
///
/// 这两个片必须是非空的，并且 `mid` 必须在范围之内。
/// 缓冲区 `buf` 必须足够长才能容纳较短切片的副本。
/// 另外，`T` 不能为零大小类型。
unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, is_less: &mut F)
where
    F: FnMut(&T, &T) -> bool,
{
    let len = v.len();
    let v = v.as_mut_ptr();

    // SAFETY: mid 和 len 必须在范围内 v.
    let (v_mid, v_end) = unsafe { (v.add(mid), v.add(len)) };

    // 合并过程首先将较短的运行复制到 `buf` 中。
    // 然后，它将跟踪新复制的运行，以及向前运行 (或向后运行) 的较长运行，比较它们的下一个未消耗元素，并将较小 (或较大) 的运行复制到 `v` 中。
    //
    // 一旦较短的运行时间被完全用尽，该过程就完成了。如果较长的运行首先被消耗，那么我们必须将较短的运行剩下的任何内容复制到 `v` 中剩余的 hole 中。
    //
    // `hole` 始终跟踪过程的中间状态，这有两个目的：
    // 1. 从 `is_less` 中的 panics 保护 `v` 的完整性。
    // 2. 如果较长时间的运行首先被消耗，则将 `v` 中剩余的 hole 填充。
    //
    // Panic 安全：
    //
    // 如果在此过程中的任何时候 `is_less` panics，`hole` 都会丢弃并用 `buf` 中的未消耗范围填充 `v` 中的 hole，从而确保 `v` 仍将其最初持有的每个对象精确地保留一次。
    //
    //
    //
    //
    //
    let mut hole;

    if mid <= len - mid {
        // 左边的运行更短。

        // SAFETY: buf 必须有足够的容量用于 `v[..mid]`。
        unsafe {
            ptr::copy_nonoverlapping(v, buf, mid);
            hole = MergeHole { start: buf, end: buf.add(mid), dest: v };
        }

        // 最初，这些指针指向其数组的开头。
        let left = &mut hole.start;
        let mut right = v_mid;
        let out = &mut hole.dest;

        while *left < hole.end && right < v_end {
            // 消耗较小的一面。
            // 如果相等，则选择左旋以保持稳定性。

            // SAFETY: left 和 right 必须有效并且 v 的一部分对于 out 相同。
            unsafe {
                let is_l = is_less(&*right, &**left);
                let to_copy = if is_l { right } else { *left };
                ptr::copy_nonoverlapping(to_copy, *out, 1);
                *out = out.add(1);
                right = right.add(is_l as usize);
                *left = left.add(!is_l as usize);
            }
        }
    } else {
        // 右边的运行更短

        // SAFETY: buf 必须有足够的容量用于 `v[mid..]`。
        unsafe {
            ptr::copy_nonoverlapping(v_mid, buf, len - mid);
            hole = MergeHole { start: buf, end: buf.add(len - mid), dest: v_mid };
        }

        // 最初，这些指针指向其数组的两端。
        let left = &mut hole.dest;
        let right = &mut hole.end;
        let mut out = v_end;

        while v < *left && buf < *right {
            // 消耗更大的一面。
            // 如果相等，则选择正确的行程以保持稳定性。

            // SAFETY: left 和 right 必须有效并且 v 的一部分对于 out 相同。
            unsafe {
                let is_l = is_less(&*right.sub(1), &*left.sub(1));
                *left = left.sub(is_l as usize);
                *right = right.sub(!is_l as usize);
                let to_copy = if is_l { *left } else { *right };
                out = out.sub(1);
                ptr::copy_nonoverlapping(to_copy, out, 1);
            }
        }
    }
    // 最后，`hole` 被丢弃。
    // 如果较短的运行没有被完全消耗，则其剩余的任何内容现在都将被复制到 `v` 的 hole 中。

    // 丢弃时，将范围 `start..end` 复制到 `dest..`。
    struct MergeHole<T> {
        start: *mut T,
        end: *mut T,
        dest: *mut T,
    }

    impl<T> Drop for MergeHole<T> {
        fn drop(&mut self) {
            // SAFETY: `T` 不是零大小的类型，它们是指向切片元素的指针。
            unsafe {
                let len = self.end.sub_ptr(self.start);
                ptr::copy_nonoverlapping(self.start, self.dest, len);
            }
        }
    }
}

/// 这个归并排序借用了一些 (但不是全部) 来自 TimSort 的想法，它曾经被详细描述在 [这里](https://github.com/python/cpython/blob/main/Objects/listsort.txt)。
/// 但是 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*))。
///
///
///
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),
{
    // 长度不超过此长度的切片将使用插入排序进行排序。
    const MAX_INSERTION: usize = 20;

    // 调用者应该已经检查过了。
    debug_assert!(!T::IS_ZST);

    let len = v.len();

    // 短数组通过插入排序进行就地排序，以避免分配。
    if len <= MAX_INSERTION {
        if len >= 2 {
            insertion_sort_shift_left(v, 1, is_less);
        }
        return;
    }

    // 分配缓冲区以用作暂存器。我们将长度保持为 0，这样就可以在其中保留 `v` 内容的浅表副本，而不会冒 `is_less` panics 在副本上运行 dtor 的风险。
    //
    // 合并两个已排序的运行时，此缓冲区将保存一个较短运行的副本，该副本的长度始终最多为 `len / 2`。
    //
    let buf = BufGuard::new(len / 2, elem_alloc_fn, elem_dealloc_fn);
    let buf_ptr = buf.buf_ptr.as_ptr();

    let mut runs = RunVec::new(run_alloc_fn, run_dealloc_fn);

    let mut end = 0;
    let mut start = 0;

    // 向前扫描。内存预取更喜欢向前扫描而不是向后扫描，代码生成通常更好。
    // 对于最敏感的类型 (如整数)，它们会立即双向合并。
    // 所以向后扫描没有任何好处。
    while end < len {
        let (streak_end, was_reversed) = find_streak(&v[start..], is_less);
        end += streak_end;
        if was_reversed {
            v[start..end].reverse();
        }

        // 如果过短，请在运行中插入更多元素。
        // 插入排序比短序列上的合并排序要快，因此可以显着提高性能。
        end = provide_sorted_batch(v, start, end, is_less);

        // 将此运行推入栈。
        runs.push(TimSortRun { start, len: end - start });
        start = end;

        // 合并一些成对的相邻行程以满足不变性。
        while let Some(r) = collapse(runs.as_slice(), len) {
            let left = runs[r];
            let right = runs[r + 1];
            let merge_slice = &mut v[left.start..right.start + right.len];
            // SAFETY: `buf_ptr` 必须为两侧中较短的一侧提供足够的容量，并且任何一侧都不能超过长度 0.
            //
            unsafe {
                merge(merge_slice, left.len, buf_ptr, is_less);
            }
            runs[r + 1] = TimSortRun { start: left.start, len: left.len + right.len };
            runs.remove(r);
        }
    }

    // 最后，必须在栈中仅保留一次运行。
    debug_assert!(runs.len() == 1 && runs[0].start == 0 && runs[0].len == len);

    // 检查运行栈，并确定要合并的下一对运行。
    // 更具体地说，如果返回 `Some(r)`，则意味着接下来必须合并 `runs[r]` 和 `runs[r + 1]`。
    // 如果算法应继续构建新的运行，则返回 `None`。
    //
    // TimSort 因其 buggy 实现而臭名昭著，如下所述：
    // http://envisage-project.eu/timsort-specification-and-verification/
    //
    // 这个故事的重点是：我们必须在栈的前四次运行中强制执行不变量。
    // 仅在前三个上强制执行它们不足以确保不变量仍然适用于栈中的所有运行。
    //
    // 此函数正确检查前四次运行的不变量。
    // 另外，如果最高运行从索引 0 开始，它将始终要求合并操作，直到栈完全展开为止，以完成排序。
    //
    //
    #[inline]
    fn collapse(runs: &[TimSortRun], stop: usize) -> Option<usize> {
        let n = runs.len();
        if n >= 2
            && (runs[n - 1].start + runs[n - 1].len == stop
                || runs[n - 2].len <= runs[n - 1].len
                || (n >= 3 && runs[n - 3].len <= runs[n - 2].len + runs[n - 1].len)
                || (n >= 4 && runs[n - 4].len <= runs[n - 3].len + runs[n - 2].len))
        {
            if n >= 3 && runs[n - 3].len < runs[n - 1].len { Some(n - 3) } else { Some(n - 2) }
        } else {
            None
        }
    }

    // Vec 的极其基本的版本。
    // 它们的使用非常有限，通过在此处提供代码，它允许在排序实现之间重用。
    //
    struct BufGuard<T, ElemDeallocF>
    where
        ElemDeallocF: Fn(*mut T, usize),
    {
        buf_ptr: ptr::NonNull<T>,
        capacity: usize,
        elem_dealloc_fn: ElemDeallocF,
    }

    impl<T, ElemDeallocF> BufGuard<T, ElemDeallocF>
    where
        ElemDeallocF: Fn(*mut T, usize),
    {
        fn new<ElemAllocF>(
            len: usize,
            elem_alloc_fn: ElemAllocF,
            elem_dealloc_fn: ElemDeallocF,
        ) -> Self
        where
            ElemAllocF: Fn(usize) -> *mut T,
        {
            Self {
                buf_ptr: ptr::NonNull::new(elem_alloc_fn(len)).unwrap(),
                capacity: len,
                elem_dealloc_fn,
            }
        }
    }

    impl<T, ElemDeallocF> Drop for BufGuard<T, ElemDeallocF>
    where
        ElemDeallocF: Fn(*mut T, usize),
    {
        fn drop(&mut self) {
            (self.elem_dealloc_fn)(self.buf_ptr.as_ptr(), self.capacity);
        }
    }

    struct RunVec<RunAllocF, RunDeallocF>
    where
        RunAllocF: Fn(usize) -> *mut TimSortRun,
        RunDeallocF: Fn(*mut TimSortRun, usize),
    {
        buf_ptr: ptr::NonNull<TimSortRun>,
        capacity: usize,
        len: usize,
        run_alloc_fn: RunAllocF,
        run_dealloc_fn: RunDeallocF,
    }

    impl<RunAllocF, RunDeallocF> RunVec<RunAllocF, RunDeallocF>
    where
        RunAllocF: Fn(usize) -> *mut TimSortRun,
        RunDeallocF: Fn(*mut TimSortRun, usize),
    {
        fn new(run_alloc_fn: RunAllocF, run_dealloc_fn: RunDeallocF) -> Self {
            // 大多数切片最多可以进行 16 次运行排序。
            const START_RUN_CAPACITY: usize = 16;

            Self {
                buf_ptr: ptr::NonNull::new(run_alloc_fn(START_RUN_CAPACITY)).unwrap(),
                capacity: START_RUN_CAPACITY,
                len: 0,
                run_alloc_fn,
                run_dealloc_fn,
            }
        }

        fn push(&mut self, val: TimSortRun) {
            if self.len == self.capacity {
                let old_capacity = self.capacity;
                let old_buf_ptr = self.buf_ptr.as_ptr();

                self.capacity = self.capacity * 2;
                self.buf_ptr = ptr::NonNull::new((self.run_alloc_fn)(self.capacity)).unwrap();

                // SAFETY: buf_ptr new 和 old 被正确分配并且 old_buf_ptr 具有 old_capacity 有效元素。
                //
                unsafe {
                    ptr::copy_nonoverlapping(old_buf_ptr, self.buf_ptr.as_ptr(), old_capacity);
                }

                (self.run_dealloc_fn)(old_buf_ptr, old_capacity);
            }

            // SAFETY: 刚刚检查了不变体。
            unsafe {
                self.buf_ptr.as_ptr().add(self.len).write(val);
            }
            self.len += 1;
        }

        fn remove(&mut self, index: usize) {
            if index >= self.len {
                panic!("Index out of bounds");
            }

            // SAFETY: buf_ptr 需要有效并且 len 不变。
            unsafe {
                // 我们要去的地方。
                let ptr = self.buf_ptr.as_ptr().add(index);

                // 向下移动所有内容以填充该位置。
                ptr::copy(ptr.add(1), ptr, self.len - index - 1);
            }
            self.len -= 1;
        }

        fn as_slice(&self) -> &[TimSortRun] {
            // SAFETY: 只要 buf_ptr 有效并且 len 不变性得到支持，它就是安全的。
            unsafe { &*ptr::slice_from_raw_parts(self.buf_ptr.as_ptr(), self.len) }
        }

        fn len(&self) -> usize {
            self.len
        }
    }

    impl<RunAllocF, RunDeallocF> core::ops::Index<usize> for RunVec<RunAllocF, RunDeallocF>
    where
        RunAllocF: Fn(usize) -> *mut TimSortRun,
        RunDeallocF: Fn(*mut TimSortRun, usize),
    {
        type Output = TimSortRun;

        fn index(&self, index: usize) -> &Self::Output {
            if index < self.len {
                // SAFETY: 必须坚持 buf_ptr 和 len 不，变体。
                unsafe {
                    return &*(self.buf_ptr.as_ptr().add(index));
                }
            }

            panic!("Index out of bounds");
        }
    }

    impl<RunAllocF, RunDeallocF> core::ops::IndexMut<usize> for RunVec<RunAllocF, RunDeallocF>
    where
        RunAllocF: Fn(usize) -> *mut TimSortRun,
        RunDeallocF: Fn(*mut TimSortRun, usize),
    {
        fn index_mut(&mut self, index: usize) -> &mut Self::Output {
            if index < self.len {
                // SAFETY: 必须坚持 buf_ptr 和 len 不，变体。
                unsafe {
                    return &mut *(self.buf_ptr.as_ptr().add(index));
                }
            }

            panic!("Index out of bounds");
        }
    }

    impl<RunAllocF, RunDeallocF> Drop for RunVec<RunAllocF, RunDeallocF>
    where
        RunAllocF: Fn(usize) -> *mut TimSortRun,
        RunDeallocF: Fn(*mut TimSortRun, usize),
    {
        fn drop(&mut self) {
            // 只要 TimSortRun 是 Copy，我们就不需要单独丢弃它们，而只需丢弃整个分配。
            //
            (self.run_dealloc_fn)(self.buf_ptr.as_ptr(), self.capacity);
        }
    }
}

/// merge_sort 使用的内部类型。
#[derive(Clone, Copy, Debug)]
pub struct TimSortRun {
    len: usize,
    start: usize,
}

/// 采用由开始和结束表示的范围，该范围已经排序，并在必要时将其扩展到右侧，并使用针对较小范围 (例如插入排序) 优化的排序。
///
fn provide_sorted_batch<T, F>(v: &mut [T], start: usize, mut end: usize, is_less: &mut F) -> usize
where
    F: FnMut(&T, &T) -> bool,
{
    let len = v.len();
    assert!(end >= start && end <= len);

    // 该值是最少比较和最佳性能之间的平衡，例如受缓存位置的影响。
    //
    const MIN_INSERTION_RUN: usize = 10;

    // 如果过短，请在运行中插入更多元素。
    // 插入排序比短序列上的合并排序要快，因此可以显着提高性能。
    let start_end_diff = end - start;

    if start_end_diff < MIN_INSERTION_RUN && end < len {
        // v [start_found..end] 是已经在输入中排序的元素。
        // 我们想将排序区域向左扩展，因此我们将 MIN_INSERTION_RUN-1 推向右侧。
        // 这比试图将那些已经排序的元素推到左边更有效。
        end = cmp::min(start + MIN_INSERTION_RUN, len);
        let presorted_start = cmp::max(start_end_diff, 1);

        insertion_sort_shift_left(&mut v[start..end], presorted_start, is_less);
    }

    end
}

/// 查找从切片开头开始的一系列预排序元素。
/// 返回不属于所述连胜的第一个值，以及表示连胜是否被反转的 bool。
/// 条纹可以增加或减少。
fn find_streak<T, F>(v: &[T], is_less: &mut F) -> (usize, bool)
where
    F: FnMut(&T, &T) -> bool,
{
    let len = v.len();

    if len < 2 {
        return (len, false);
    }

    let mut end = 2;

    // SAFETY: 具体见下文。
    unsafe {
        // SAFETY: 我们检查了 len >= 2，因此 0 和 1 是有效索引。
        let assume_reverse = is_less(v.get_unchecked(1), v.get_unchecked(0));

        // SAFETY: 我们知道 end >= 2 并检查 end < len。
        // 由此可见，在 end 和 end-1 处访问 v 是安全的。
        if assume_reverse {
            while end < len && is_less(v.get_unchecked(end), v.get_unchecked(end - 1)) {
                end += 1;
            }

            (end, true)
        } else {
            while end < len && !is_less(v.get_unchecked(end), v.get_unchecked(end - 1)) {
                end += 1;
            }
            (end, false)
        }
    }
}