1//! This module contains the entry points for `slice::sort_unstable`.
2
3use crate::mem::SizedTypeProperties;
4use crate::ops::{Range, RangeBounds};
5use crate::slice::sort::select::partition_at_index;
6#[cfg(not(any(feature = "optimize_for_size", target_pointer_width = "16")))]
7use crate::slice::sort::shared::find_existing_run;
8#[cfg(not(any(feature = "optimize_for_size", target_pointer_width = "16")))]
9use crate::slice::sort::shared::smallsort::insertion_sort_shift_left;
10use crate::{cfg_select, intrinsics, slice};
11
12pub(crate) mod heapsort;
13pub(crate) mod quicksort;
14
15/// Unstable sort called ipnsort by Lukas Bergdoll and Orson Peters.
16/// Design document:
17/// <https://github.com/Voultapher/sort-research-rs/blob/main/writeup/ipnsort_introduction/text.md>
18///
19/// Upholds all safety properties outlined here:
20/// <https://github.com/Voultapher/sort-research-rs/blob/main/writeup/sort_safety/text.md>
21#[inline(always)]
22pub fn sort<T, F>(v: &mut [T], is_less: &mut F)
23where
24 F: FnMut(&T, &T) -> bool,
25{
26 // Arrays of zero-sized types are always all-equal, and thus sorted.
27 if T::IS_ZST {
28 return;
29 }
30
31 // Instrumenting the standard library showed that 90+% of the calls to sort
32 // by rustc are either of size 0 or 1.
33 let len = v.len();
34 if intrinsics::likely(len < 2) {
35 return;
36 }
37
38 cfg_select! {
39 any(feature = "optimize_for_size", target_pointer_width = "16") => {
40 heapsort::heapsort(v, is_less);
41 }
42 _ => {
43 // More advanced sorting methods than insertion sort are faster if called in
44 // a hot loop for small inputs, but for general-purpose code the small
45 // binary size of insertion sort is more important. The instruction cache in
46 // modern processors is very valuable, and for a single sort call in general
47 // purpose code any gains from an advanced method are cancelled by i-cache
48 // misses during the sort, and thrashing the i-cache for surrounding code.
49 const MAX_LEN_ALWAYS_INSERTION_SORT: usize = 20;
50 if intrinsics::likely(len <= MAX_LEN_ALWAYS_INSERTION_SORT) {
51 insertion_sort_shift_left(v, 1, is_less);
52 return;
53 }
54
55 ipnsort(v, is_less);
56 }
57 }
58}
59
60/// Unstable partial sort the range `start..end`, after which it's guaranteed that:
61///
62/// 1. Every element in `v[..start]` is smaller than or equal to
63/// 2. Every element in `v[start..end]`, which is sorted, and smaller than or equal to
64/// 3. Every element in `v[end..]`.
65#[inline]
66pub fn partial_sort<T, F, R>(v: &mut [T], range: R, mut is_less: F)
67where
68 F: FnMut(&T, &T) -> bool,
69 R: RangeBounds<usize>,
70{
71 // Arrays of zero-sized types are always all-equal, and thus sorted.
72 if T::IS_ZST {
73 return;
74 }
75
76 let len = v.len();
77 let Range { start, end } = slice::range(range, ..len);
78
79 if end - start <= 1 {
80 // Empty range or single element. This case can be resolved in at most
81 // single partition_at_index call, without further sorting.
82
83 if end == 0 || start == len {
84 // Do nothing if it is an empty range at start or end: all guarantees
85 // are already upheld.
86 return;
87 }
88
89 partition_at_index(v, start, &mut is_less);
90 return;
91 }
92
93 // A heuristic factor to decide whether to partition the slice or not.
94 // If the range bound is close to the edges of the slice, it's not worth
95 // partitioning first.
96 const PARTITION_THRESHOLD: usize = 8;
97 let mut v = v;
98 if end + PARTITION_THRESHOLD <= len {
99 v = partition_at_index(v, end - 1, &mut is_less).0;
100 }
101 if start >= PARTITION_THRESHOLD {
102 v = partition_at_index(v, start, &mut is_less).2;
103 }
104
105 sort(v, &mut is_less);
106}
107
108/// See [`sort`]
109///
110/// Deliberately don't inline the main sorting routine entrypoint to ensure the
111/// inlined insertion sort i-cache footprint remains minimal.
112#[cfg(not(any(feature = "optimize_for_size", target_pointer_width = "16")))]
113#[inline(never)]
114fn ipnsort<T, F>(v: &mut [T], is_less: &mut F)
115where
116 F: FnMut(&T, &T) -> bool,
117{
118 let len: usize = v.len();
119 let (run_len: usize, was_reversed: bool) = find_existing_run(v, is_less);
120
121 // SAFETY: find_existing_run promises to return a valid run_len.
122 unsafe { intrinsics::assume(run_len <= len) };
123
124 if run_len == len {
125 if was_reversed {
126 v.reverse();
127 }
128
129 // It would be possible to a do in-place merging here for a long existing streak. But that
130 // makes the implementation a lot bigger, users can use `slice::sort` for that use-case.
131 return;
132 }
133
134 // Limit the number of imbalanced partitions to `2 * floor(log2(len))`.
135 // The binary OR by one is used to eliminate the zero-check in the logarithm.
136 let limit: u32 = 2 * (len | 1).ilog2();
137 crate::slice::sort::unstable::quicksort::quicksort(v, ancestor_pivot:None, limit, is_less);
138}
139