core/slice/sort/unstable/
mod.rs

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 = v.len();
119    let (run_len, was_reversed) = 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 = 2 * (len | 1).ilog2();
137    crate::slice::sort::unstable::quicksort::quicksort(v, None, limit, is_less);
138}
core/slice/sort/unstable/mod.rs

core/slice/sort/unstable/
mod.rs
