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

// ignore-tidy-undocumented-unsafe

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

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

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

/// 将第一个元素向右移动，直到遇到一个更大或相等的元素。
fn shift_head<T, F>(v: &mut [T], is_less: &mut F)
where
    F: FnMut(&T, &T) -> bool,
{
    let len = v.len();
    // SAFETY: 下面的不安全操作涉及没有绑定检查 (`get_unchecked` 和 `get_unchecked_mut`) 的索引以及复制存储器 (`ptr::copy_nonoverlapping`)。
    //
    //
    // a. Indexing:
    //  1. 我们将数组的大小检查为 >= 2。
    //  2. 我们将要进行的所有索引编制最多始终在 {0 <= index < len} 之间。
    //
    // b. 内存复制
    //  1. 我们正在获得指向 quot 的指针，这些指针被保证是有效的。
    //  2. 它们不能重叠，因为我们获得了指向切片的不同索引的指针。
    //     即 `i` 和 `i-1`。
    //  3. 如果切片正确对齐，则元素正确对齐。
    //     确保切片正确对齐是调用者的责任。
    //
    // 有关更多详细信息，请参见下面的评论。
    unsafe {
        // 如果前两个元素乱序...
        if len >= 2 && is_less(v.get_unchecked(1), v.get_unchecked(0)) {
            // 将第一个元素读取到栈分配的变量中。
            // 如果执行以下比较操作 panics，则 `hole` 将被丢弃并自动将元素写回到切片中。
            //
            let mut tmp = mem::ManuallyDrop::new(ptr::read(v.get_unchecked(0)));
            let mut hole = CopyOnDrop { src: &mut *tmp, dest: v.get_unchecked_mut(1) };
            ptr::copy_nonoverlapping(v.get_unchecked(1), v.get_unchecked_mut(0), 1);

            for i in 2..len {
                if !is_less(v.get_unchecked(i), &*tmp) {
                    break;
                }

                // 将第 i 个元素向左移动一个位置，从而将 hole 向右移动。
                ptr::copy_nonoverlapping(v.get_unchecked(i), v.get_unchecked_mut(i - 1), 1);
                hole.dest = v.get_unchecked_mut(i);
            }
            // `hole` 被丢弃，从而将 `tmp` 复制到 `v` 中剩余的 hole 中。
        }
    }
}

/// 将最后一个元素向左移动，直到遇到一个较小或相等的元素。
fn shift_tail<T, F>(v: &mut [T], is_less: &mut F)
where
    F: FnMut(&T, &T) -> bool,
{
    let len = v.len();
    // SAFETY: 下面的不安全操作涉及没有绑定检查 (`get_unchecked` 和 `get_unchecked_mut`) 的索引以及复制存储器 (`ptr::copy_nonoverlapping`)。
    //
    //
    // a. Indexing:
    //  1. 我们将数组的大小检查为 >= 2。
    //  2. 我们将要进行的所有索引编制最多始终在 `0 <= index < len-1` 之间。
    //
    // b. 内存复制
    //  1. 我们正在获得指向 quot 的指针，这些指针被保证是有效的。
    //  2. 它们不能重叠，因为我们获得了指向切片的不同索引的指针。
    //     即 `i` 和 `i+1`。
    //  3. 如果切片正确对齐，则元素正确对齐。
    //     确保切片正确对齐是调用者的责任。
    //
    // 有关更多详细信息，请参见下面的评论。
    unsafe {
        // 如果最后两个元素乱序...
        if len >= 2 && is_less(v.get_unchecked(len - 1), v.get_unchecked(len - 2)) {
            // 将最后一个元素读取到栈分配的变量中。
            // 如果执行以下比较操作 panics，则 `hole` 将被丢弃并自动将元素写回到切片中。
            //
            let mut tmp = mem::ManuallyDrop::new(ptr::read(v.get_unchecked(len - 1)));
            let mut hole = CopyOnDrop { src: &mut *tmp, dest: v.get_unchecked_mut(len - 2) };
            ptr::copy_nonoverlapping(v.get_unchecked(len - 2), v.get_unchecked_mut(len - 1), 1);

            for i in (0..len - 2).rev() {
                if !is_less(&*tmp, v.get_unchecked(i)) {
                    break;
                }

                // 将第 i 个元素向右移动一个位置，从而将 hole 向左移动。
                ptr::copy_nonoverlapping(v.get_unchecked(i), v.get_unchecked_mut(i + 1), 1);
                hole.dest = v.get_unchecked_mut(i);
            }
            // `hole` 被丢弃，从而将 `tmp` 复制到 `v` 中剩余的 hole 中。
        }
    }
}

/// 通过移动几个乱序的元素来对切片进行部分排序。
///
/// 如果切片末尾排序，则返回 `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);

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

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

/// 使用插入排序对切片进行排序，这是 *O*(*n*^ 2) 最坏的情况。
fn insertion_sort<T, F>(v: &mut [T], is_less: &mut F)
where
    F: FnMut(&T, &T) -> bool,
{
    for i in 1..v.len() {
        shift_tail(&mut v[..i + 1], is_less);
    }
}

/// 使用堆排序对 `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 left = 2 * node + 1;
            let right = 2 * node + 2;

            // 选择更大的子节点。
            let greater =
                if right < v.len() && is_less(&v[left], &v[right]) { right } else { left };

            // 如果不可变变量位于 `node`，则停止。
            if greater >= v.len() || !is_less(&v[node], &v[greater]) {
                break;
            }

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

    // 在线性时间内构建堆。
    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. 偏移量 - 块内乱序元素的索引。

    // 左侧的当前块 (从 `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);
        (r as usize - l as usize) / 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 = MaybeUninit::slice_as_mut_ptr(&mut offsets_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.offset(!is_less(&*elem, pivot) as isize);
                    elem = elem.offset(1);
                }
            }
        }

        if start_r == end_r {
            // 从右侧跟踪 `block_r` 元素。
            start_r = MaybeUninit::slice_as_mut_ptr(&mut offsets_r);
            end_r = MaybeUninit::slice_as_mut_ptr(&mut offsets_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.offset(-1);
                    *end_r = i as u8;
                    end_r = end_r.offset(is_less(&*elem, pivot) as isize);
                }
            }
        }

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

        if count > 0 {
            macro_rules! left {
                () => {
                    l.offset(*start_l as isize)
                };
            }
            macro_rules! right {
                () => {
                    r.offset(-(*start_r as isize) - 1)
                };
            }

            // 与一次交换一对相比，执行循环置换更为有效。
            // 这并不严格等同于交换，但是使用较少的内存操作即可产生类似的结果。
            //
            unsafe {
                let tmp = ptr::read(left!());
                ptr::copy_nonoverlapping(right!(), left!(), 1);

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

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

        if start_l == end_l {
            // 左侧块中的所有乱序元素均已移动。移至下一个块。
            l = unsafe { l.offset(block_l as isize) };
        }

        if start_r == end_r {
            // 右侧块中的所有乱序元素均已移动。移至上一个块。
            r = unsafe { r.offset(-(block_r as isize)) };
        }

        if is_done {
            break;
        }
    }

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

    if start_l < end_l {
        // 剩下的方块仍然保留。
        // 将其剩余的乱序元素移到最右边。
        debug_assert_eq!(width(l, r), block_l);
        while start_l < end_l {
            unsafe {
                end_l = end_l.offset(-1);
                ptr::swap(l.offset(*end_l as isize), r.offset(-1));
                r = r.offset(-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 {
            unsafe {
                end_r = end_r.offset(-1);
                ptr::swap(l, r.offset(-(*end_r as isize) - 1));
                l = l.offset(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。
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，则枢轴将自动写回到切片中。
        let mut tmp = mem::ManuallyDrop::new(unsafe { ptr::read(pivot) });
        let _pivot_guard = CopyOnDrop { src: &mut *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` 离开作用域，并将枢轴 (这是一个栈分配的变量) 写回到其原始位置的切片中。
        // 这一步对于确保安全至关重要!
        //
    };

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

    (mid, was_partitioned)
}

/// 将 `v` 划分为等于 `v[pivot]` 的元素，后跟大于 `v[pivot]` 的元素。
///
/// 返回等于枢轴的元素数。
/// 假定 `v` 不包含小于枢轴的元素。
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 mut tmp = mem::ManuallyDrop::new(unsafe { ptr::read(pivot) });
    let _pivot_guard = CopyOnDrop { src: &mut *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;
            ptr::swap(v.get_unchecked_mut(l), v.get_unchecked_mut(r));
            l += 1;
        }
    }

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

    // `_pivot_guard` 离开作用域，并将枢轴 (这是一个栈分配的变量) 写回到其原始位置的切片中。
    // 这一步对于确保安全至关重要!
}

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

        // 取该数字取模的随机数。
        // 该数字适合 `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` 中的元素可能会在此过程中重新排序。
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]`。
        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 {
            insertion_sort(v, 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);

        // 如果最后一个分区达到了合理的平衡并且没有使元素混洗，并且如果枢轴选择预测了切片，则该切片可能已经被排序了...
        //
        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 mem::size_of::<T>() == 0 {
        return;
    }

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

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

fn partition_at_index_loop<'a, T, F>(
    mut v: &'a mut [T],
    mut index: usize,
    is_less: &mut F,
    mut pred: Option<&'a T>,
) where
    F: FnMut(&T, &T) -> bool,
{
    loop {
        // 对于不超过此长度的切片，将其简单排序可能会更快。
        const MAX_INSERTION: usize = 10;
        if v.len() <= MAX_INSERTION {
            insertion_sort(v, is_less);
            return;
        }

        // 选择一个 pivot
        let (pivot, _) = choose_pivot(v, is_less);

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

                // 如果我们通过了索引，那么我们就很好。
                if mid > index {
                    return;
                }

                // 否则，继续对大于枢轴的元素进行排序。
                v = &mut v[mid..];
                index = index - mid;
                pred = None;
                continue;
            }
        }

        let (mid, _) = partition(v, pivot, is_less);

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

        if mid < index {
            v = right;
            index = index - mid - 1;
            pred = Some(pivot);
        } else if mid > index {
            v = left;
        } else {
            // 如果 mid == index，那么我们就完成了，因为 partition() 保证 mid 之后的所有元素都大于或等于 mid。
            //
            return;
        }
    }
}

pub fn partition_at_index<T, F>(
    v: &mut [T],
    index: usize,
    mut is_less: F,
) -> (&mut [T], &mut T, &mut [T])
where
    F: FnMut(&T, &T) -> bool,
{
    use cmp::Ordering::Greater;
    use cmp::Ordering::Less;

    if index >= v.len() {
        panic!("partition_at_index index {} greater than length of slice {}", index, v.len());
    }

    if mem::size_of::<T>() == 0 {
        // 零大小类型的排序没有有意义的行为。没做什么。
    } else if index == v.len() - 1 {
        // 查找最大元素并将其放置在数组的最后一个位置。
        // 我们可以在这里自由使用 `unwrap()`，因为我们知道 v 不能为空。
        let (max_index, _) = v
            .iter()
            .enumerate()
            .max_by(|&(_, x), &(_, y)| if is_less(x, y) { Less } else { Greater })
            .unwrap();
        v.swap(max_index, index);
    } else if index == 0 {
        // 查找 min 元素并将其放置在数组的第一个位置。
        // 我们可以在这里自由使用 `unwrap()`，因为我们知道 v 不能为空。
        let (min_index, _) = v
            .iter()
            .enumerate()
            .min_by(|&(_, x), &(_, y)| if is_less(x, y) { Less } else { Greater })
            .unwrap();
        v.swap(min_index, index);
    } else {
        partition_at_index_loop(v, index, &mut is_less, None);
    }

    let (left, right) = v.split_at_mut(index);
    let (pivot, right) = right.split_at_mut(1);
    let pivot = &mut pivot[0];
    (left, pivot, right)
}