core/slice/sort/unstable/
heapsort.rs

Help
1//! This module contains a branchless heapsort as fallback for unstable quicksort.
2
3use crate::{cmp, intrinsics, ptr};
4
5/// Sorts `v` using heapsort, which guarantees *O*(*n* \* log(*n*)) worst-case.
6///
7/// Never inline this, it sits the main hot-loop in `recurse` and is meant as unlikely algorithmic
8/// fallback.
9#[inline(never)]
10pub(crate) fn heapsort<T, F>(v: &mut [T], is_less: &mut F)
11where
12    F: FnMut(&T, &T) -> bool,
13{
14    let len = v.len();
15
16    for i in (0..len + len / 2).rev() {
17        let sift_idx = if i >= len {
18            i - len
19        } else {
20            v.swap(0, i);
21            0
22        };
23
24        // SAFETY: The above calculation ensures that `sift_idx` is either 0 or
25        // `(len..(len + (len / 2))) - len`, which simplifies to `0..(len / 2)`.
26        // This guarantees the required `sift_idx <= len`.
27        unsafe {
28            sift_down(&mut v[..cmp::min(i, len)], sift_idx, is_less);
29        }
30    }
31}
32
33// This binary heap respects the invariant `parent >= child`.
34//
35// SAFETY: The caller has to guarantee that `node <= v.len()`.
36#[inline(always)]
37unsafe fn sift_down<T, F>(v: &mut [T], mut node: usize, is_less: &mut F)
38where
39    F: FnMut(&T, &T) -> bool,
40{
41    // SAFETY: See function safety.
42    unsafe {
43        intrinsics::assume(node <= v.len());
44    }
45
46    let len = v.len();
47
48    let v_base = v.as_mut_ptr();
49
50    loop {
51        // Children of `node`.
52        let mut child = 2 * node + 1;
53        if child >= len {
54            break;
55        }
56
57        // SAFETY: The invariants and checks guarantee that both node and child are in-bounds.
58        unsafe {
59            // Choose the greater child.
60            if child + 1 < len {
61                // We need a branch to be sure not to out-of-bounds index,
62                // but it's highly predictable.  The comparison, however,
63                // is better done branchless, especially for primitives.
64                child += is_less(&*v_base.add(child), &*v_base.add(child + 1)) as usize;
65            }
66
67            // Stop if the invariant holds at `node`.
68            if !is_less(&*v_base.add(node), &*v_base.add(child)) {
69                break;
70            }
71
72            ptr::swap_nonoverlapping(v_base.add(node), v_base.add(child), 1);
73        }
74
75        node = child;
76    }
77}
core/slice/sort/unstable/heapsort.rs

core/slice/sort/unstable/
heapsort.rs
