1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
//! 切片分类
//!
//! 该模块包含基于 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)
        }
    }
}