nettrash-a 0.0.28

use core::mem::{self, MaybeUninit};
use core::{ptr, slice};

use super::key::IntegerKey;
use super::tim::Buffer;

/// Sorts a slice of integers, `char`s or `bool`s in place using counting sort.
///
/// Counting sort, described by Harold Seward in 1954, does not compare elements with each other.
/// It finds the smallest and the largest value, counts how many times each of the `k` values in
/// between occurs, and rewrites the slice from the counts: so many copies of the smallest value,
/// then so many of the next, and so on. That takes `O(n + k)` time and `O(k)` memory whatever the
/// order of the input, which beats every comparison sort when `k` is not much larger than `n`:
/// bytes, small integers, values in a known range.
///
/// Equal values of these types cannot be told apart, so rewriting them from counts sorts the
/// slice exactly as moving them would. [`counting_by_key`] sorts any type by such a key, moving
/// the elements and keeping equal keys in order.
///
/// Four refinements keep the algorithm as cheap as counting sort can be:
///
/// * **Sorted and reverse-sorted input is recognised.** The slice is first scanned for one
///   ascending or one non-increasing run, 16 neighbours at a time with no exit inside a block,
///   which the compiler vectorizes; if it covers the whole slice, the slice is left alone or
///   reversed, and nothing is counted. Random input leaves the scan after the first block.
/// * **Eight count tables for small ranges.** Incrementing a count waits for the increment
///   before it to reach memory, so a run of equal values, or a few values repeating, makes a
///   chain of dependent increments. With at most 2048 values and at least 16 elements per value,
///   the slice is counted into eight tables, one element after the other into the next, and the
///   tables are added up: eight chains at once, 3–5 times faster with a few distinct values and
///   on sorted runs of bytes. One table is counted as four quarters of the slice side by side,
///   which breaks such chains too, when its counts are `u16` or the slice's first values are
///   mostly in order: 2.2 times faster on nearly sorted input with sixteen of each value. With
///   that walk for `u16` counts, and a plain loop for wider ones that it stays out of the way of,
///   random `u8` and `u32` values from 100 elements on sort 1.05–1.3 times faster than with one
///   plain loop for every count type; wider values as fast.
/// * **Values written ahead of their counts.** Each value is written 4 times (8 for one- and
///   two-byte types, in one store) whatever its count, and only a count above that takes a
///   branch; the copies beyond the count are overwritten by the next value. Branching on every
///   count mispredicts when the range has about as many values as the slice has elements, where
///   counts of 0, 1 and 2 are all common: this is 2.5–5 times faster there. A range with 32 or more
///   values per element is rewritten instead by skipping blocks of 8 empty counts at once.
/// * **Counts on the stack.** Up to 4 KiB of counts (2048 values, or 256 values in eight tables,
///   up to 65,535 elements) need no allocation; counts are `u16` up to 65,535 elements and `u32`
///   up to `u32::MAX`, a quarter and a half of the memory larger ranges take (1.1–1.25 times
///   faster at 10,000–50,000 elements than `u32` counts).
///
/// Together, against the textbook counting sort (scan for the range, count, branch on every
/// count to rewrite): 3–5.5 times faster on random integers with about as many distinct values
/// as elements, 1.9–3.1 times with four times as many and 1.05–1.45 times with sixteen times
/// fewer; 1.7–3.1 times faster with four distinct values, 3.1–4.7 times on nearly sorted input,
/// and 9–80 times on sorted, reverse-sorted and all-equal input. Random bytes cost the same as
/// with the textbook sort from 10,000 elements on; 16 random bytes are 1.4 times slower, as
/// writing ahead does not pay for a range 15 times longer than the slice.
///
/// # Properties
///
/// * **Stable** in effect: equal values cannot be told apart.
/// * **Not in place**: `O(k)` counts, on the stack up to 4 KiB and otherwise allocated once.
/// * **Not adaptive**, except to sorted and reverse-sorted input.
///
/// | Case                          | Passes over the slice                           | Time       |
/// |-------------------------------|-------------------------------------------------|------------|
/// | Sorted, reverse-sorted, equal | one scan (`n − 1` comparisons), reversing        | `O(n)`     |
/// | Any other input               | a block or two of the scan, range, count, write | `O(n + k)` |
///
/// Against [`slice::sort_unstable`], for `u32` and `u64` from 100 elements on: 3.2–10 times faster
/// on random integers with about as many distinct values as elements, 2.8–14 times with
/// sixteen times fewer, 1.9–4 times with four times as many, 2.8–4 times with four distinct
/// values; 2.2–12 times faster on nearly sorted input, 1.6–4.8 times on sorted and all-equal input,
/// and 12–99 times on reverse-sorted input; random bytes sort 9–15 times faster from 1000
/// elements on. On 16 elements it is up to 2 times slower on sorted, nearly sorted and all-equal
/// input, and this crate's [`drift`](fn@super::drift) sort, which insertion sorts short slices,
/// is up to twice as fast on most input.
///
/// # Panics
///
/// Panics if the range is too large to count: if `max − min + 1` exceeds both 65,536 and four
/// times the length of the slice, whatever the order of the slice. The slice is then left as it
/// was. Any range of a one- or two-byte type is allowed.
///
/// # Examples
///
/// ```
/// use a::sort::counting;
///
/// let mut v = [5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
/// counting(&mut v);
/// assert_eq!(v, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
///
/// // Any integer type, signed ones too, as long as the range is small.
/// let mut v = [i64::MIN + 2, i64::MIN, i64::MIN + 1];
/// counting(&mut v);
/// assert_eq!(v, [i64::MIN, i64::MIN + 1, i64::MIN + 2]);
///
/// let mut letters: Vec<char> = "counting".chars().collect();
/// counting(&mut letters);
/// assert_eq!(letters.iter().collect::<String>(), "cginnotu");
/// ```
///
/// A range too large for the slice panics:
///
/// ```should_panic
/// use a::sort::counting;
///
/// let mut v = [0u32, 1_000_000];
/// counting(&mut v);
/// ```
pub fn counting<T: IntegerKey>(arr: &mut [T]) {
    let len = arr.len();
    if len < 2 {
        return;
    }
    // Sorted input has nothing to count, but its range is checked all the same: the limit does
    // not depend on the order of the elements.
    if in_order(arr, |x, y| y < x) {
        range(arr[0], arr[len - 1], len, SORT);
        return;
    }
    // Equal values cannot be told apart, so a non-increasing slice only needs reversing.
    if in_order(arr, |x, y| y > x) {
        range(arr[len - 1], arr[0], len, SORT);
        arr.reverse();
        return;
    }
    let (min, max) = min_max(arr);
    let k = range(min, max, len, SORT);
    if len <= u16::MAX as usize {
        rewrite::<T, u16>(arr, min, k);
    } else if len <= u32::MAX as usize {
        rewrite::<T, u32>(arr, min, k);
    } else {
        rewrite::<T, usize>(arr, min, k);
    }
}

/// Sorts a slice in place by an integer, `char` or `bool` key using counting sort. The sort is
/// stable: elements with equal keys keep their order.
///
/// This is counting sort as it is used inside radix sort: the keys are counted, the counts are
/// turned into the place where each key's elements begin, and every element is moved, in order,
/// to the next place of its key in a buffer of `n` elements, which is then copied back. It takes
/// `O(n + k)` time for `k = max − min + 1` possible keys, and `O(n + k)` memory.
///
/// `key` is called exactly once per element: the keys are kept in a buffer of their own as they
/// are read. That costs `n` keys of memory and a few percent on input whose elements carry their
/// keys in order, but it makes the sort as fast as possible on random keys, lets the counts and
/// places be trusted without checking them, and leaves the slice untouched if `key` panics.
///
/// Four refinements keep the algorithm as cheap as counting sort can be:
///
/// * **Sorted and strictly descending input is recognised**, in the same pass that reads the keys
///   and finds the range: the slice is then left alone or reversed. Input that is descending but
///   not strictly is sorted like any other, as reversing it would swap equal keys.
/// * **Eight segments for small ranges.** Placing an element waits for the place handed out
///   before it to the same key, so a few keys repeating make a chain of dependent increments.
///   With at most 256 keys and at least 16 elements per key, the slice is cut into eight
///   segments, each with its own places for every key after those of the segments before it,
///   and the segments are counted and placed side by side: eight chains at once, 1.6–2.3 times
///   faster with four distinct keys and 2.4–2.9 times on runs of bytes. More keys than 256 gain
///   nothing and lose up to 1.25 times to the extra places. One segment is counted as four
///   quarters side by side instead, as counts do not depend on the order of the keys, and placed
///   four keys at a time, all four places read before any is written back: 1.4–2.6 times faster
///   on nearly sorted input, 1.1–1.25 times on random keys over four times as many keys as
///   elements.
/// * **Keys read once.** Counting and placing read the keys from their buffer instead of from
///   the elements: 1.05–1.25 times faster than calling `key` again on random keys with about as
///   many distinct keys as elements, or four times as many.
/// * **Buffers on the stack.** Up to 4 KiB each of elements, keys and places (places are `u16`
///   up to 65,535 elements in one segment, which halves the memory they take, and `u32` up to
///   `u32::MAX` elements otherwise) need no allocation.
///
/// Together, against the textbook counting sort (scan for the range, count, place, copy back,
/// calling `key` in each pass): 1.05–1.6 times faster on random keys, 1.35–2.2 times with four
/// distinct keys, 2.6–3.1 times on runs of bytes and 6–20 times on sorted and all-equal input;
/// but 1.02–1.15 times slower on reverse-sorted input with repeated keys, on random bytes from
/// 10,000 elements on and on 1000–10,000 random keys with sixteen times fewer keys than
/// elements, where keeping the keys costs more than it saves. Nearly sorted input, 1.02–1.15
/// times slower than the textbook sort before keys were placed four at a time, now takes
/// 0.6–0.85 times as long as it did then.
///
/// # Properties
///
/// * **Stable**: elements with equal keys keep their order.
/// * **Not in place**: a buffer of `n` elements, one of `n` keys and `O(k)` places, each on the
///   stack up to 4 KiB and otherwise allocated once. Sorted input over 4 KiB of keys still
///   allocates the keys, which are kept as they are read.
/// * **Not adaptive**, except to sorted and strictly descending input.
///
/// | Case                         | Calls to `key` | Passes over the slice                | Time       |
/// |------------------------------|----------------|--------------------------------------|------------|
/// | Sorted, strictly descending  | `n`            | one, reversing                       | `O(n)`     |
/// | Any other input              | `n`            | read keys, count, place, copy back   | `O(n + k)` |
///
/// Against [`slice::sort_by_key`], with 16-byte elements from 100 elements on: 3–7.6 times faster
/// on random `u32` keys with sixteen times fewer distinct keys than elements, 2.9–7 times with
/// about as many, 1.85–4.2 times with four times as many; 1.6–2.3 times faster with four
/// distinct keys, 1.9–5.7 times on reverse-sorted input and 1.6–9 times on nearly sorted input;
/// as fast on sorted and all-equal input with `u32` keys, and 1.3–1.7 times faster with `u8`
/// keys from 1000 elements on, where random bytes sort 4.4–8 times faster. On 16 elements it is
/// between 1.9 times faster and 2 times slower.
///
/// # Panics
///
/// Panics if the range of keys is too large to count, as [`counting`] does; the slice is then
/// left as it was. If `key` panics, the panic is propagated and the slice is left as it was: no
/// element has been moved before the last key is read.
///
/// # Examples
///
/// ```
/// use a::sort::counting_by_key;
///
/// let mut v = [(3, 'a'), (1, 'b'), (3, 'c'), (0, 'd'), (1, 'e')];
/// counting_by_key(&mut v, |&(k, _)| k);
/// assert_eq!(v, [(0, 'd'), (1, 'b'), (1, 'e'), (3, 'a'), (3, 'c')]);
///
/// // Words by length; equal lengths keep their order.
/// let mut words = vec!["pear", "fig", "banana", "kiwi", "apple", "lime"];
/// counting_by_key(&mut words, |w| w.len());
/// assert_eq!(words, ["fig", "pear", "kiwi", "lime", "apple", "banana"]);
/// ```
pub fn counting_by_key<T, K, F>(arr: &mut [T], mut key: F)
where
    K: IntegerKey,
    F: FnMut(&T) -> K,
{
    let len = arr.len();
    if len < 2 || mem::size_of::<T>() == 0 {
        return;
    }
    let mut stack = Stack([MaybeUninit::uninit(); STACK_BYTES]);
    let mut heap = Vec::new();
    let slots = key_slots::<K>(len, &mut stack, &mut heap);
    let first = key(&arr[0]);
    slots[0].write(first);
    let (mut min, mut max, mut prev) = (first, first, first);
    let (mut descent, mut no_descent) = (false, false);
    for (slot, x) in slots[1..].iter_mut().zip(&arr[1..]) {
        let x = key(x);
        slot.write(x);
        min = min.min(x);
        max = max.max(x);
        descent |= x < prev;
        no_descent |= x >= prev;
        prev = x;
    }
    // SAFETY: all `len` slots have been written.
    let keys = unsafe { slice::from_raw_parts(slots.as_ptr().cast::<K>(), len) };
    let k = range(min, max, len, SORT);
    if !descent {
        return;
    }
    // Strictly descending: reversing it keeps the order of equal keys, as there are none.
    if !no_descent {
        arr.reverse();
        return;
    }
    scatter(arr, keys, min, k);
}

/// The name a range too large panics with.
const SORT: &str = "counting sort";

/// Every range of at most this many values is allowed, whatever the length of the slice.
const RANGE_MIN: usize = 1 << 16;

/// Beyond [`RANGE_MIN`], a range is allowed if it has at most this many values per element.
const RANGE_PER_ELEMENT: usize = 4;

/// Returns the number of values from `min` to `max`, or panics, naming `sort`, if there are too
/// many to count for `len` elements.
pub(super) fn range<K: IntegerKey>(min: K, max: K, len: usize, sort: &str) -> usize {
    let limit = RANGE_MIN.max(len.saturating_mul(RANGE_PER_ELEMENT));
    let distance = max.distance(min);
    match usize::try_from(distance) {
        Ok(d) if d < limit => d + 1,
        _ => panic!(
            "{sort}: {} possible values are too many for {len} elements (at most {limit})",
            distance.saturating_add(1)
        ),
    }
}

/// Whether no two neighbours `x, y` of `v` are `out(x, y)`. The pairs are checked in blocks of
/// 16 with no exit inside a block, which the compiler vectorizes; random input leaves after the
/// first block.
#[inline(always)]
pub(super) fn in_order<T: Copy>(v: &[T], out: impl Fn(T, T) -> bool) -> bool {
    const BLOCK: usize = 16;
    let mut i = 0;
    while i + BLOCK < v.len() {
        let b = &v[i..i + BLOCK + 1];
        let mut any = false;
        for j in 0..BLOCK {
            any |= out(b[j], b[j + 1]);
        }
        if any {
            return false;
        }
        i += BLOCK;
    }
    v[i..].windows(2).all(|w| !out(w[0], w[1]))
}

/// The first this many elements tell [`in_order_at_first`]...
const HEAD: usize = 64;

/// ...whether at most one in this many of them is less than the one before it.
const HEAD_DESCENTS_PART: usize = 16;

/// Whether the first [`HEAD`] elements of `v` are mostly in order, as those of nearly sorted
/// input are: few of them less than the one before it. A cheap guess at the order of the
/// whole slice, for choosing how to count it.
#[inline(always)]
pub(super) fn in_order_at_first<T: Copy + Ord>(v: &[T]) -> bool {
    let head = &v[..v.len().min(HEAD)];
    let descents: usize = head.windows(2).map(|w| usize::from(w[1] < w[0])).sum();
    descents * HEAD_DESCENTS_PART <= head.len()
}

/// Returns the smallest and the largest value of a nonempty slice.
#[inline(always)]
pub(super) fn min_max<T: IntegerKey>(v: &[T]) -> (T, T) {
    let first = v[0];
    v.iter()
        .fold((first, first), |(min, max), &x| (min.min(x), max.max(x)))
}

/// A counter of elements: `u32` while the slice is short enough, which halves the memory the
/// counts take, and `usize` otherwise; [`pigeonhole`](fn@super::pigeonhole) sort also uses
/// `u16` up to `u16::MAX` elements.
///
/// # Safety
///
/// All-zero bytes must be a valid zero.
pub(super) unsafe trait Count: Copy + Eq {
    const ZERO: Self;
    fn add(self, n: usize) -> Self;
    fn get(self) -> usize;
}

unsafe impl Count for u32 {
    const ZERO: Self = 0;
    #[inline(always)]
    fn add(self, n: usize) -> Self {
        self + n as u32
    }
    #[inline(always)]
    fn get(self) -> usize {
        self as usize
    }
}

unsafe impl Count for u16 {
    const ZERO: Self = 0;
    #[inline(always)]
    fn add(self, n: usize) -> Self {
        self + n as u16
    }
    #[inline(always)]
    fn get(self) -> usize {
        self as usize
    }
}

unsafe impl Count for usize {
    const ZERO: Self = 0;
    #[inline(always)]
    fn add(self, n: usize) -> Self {
        self + n
    }
    #[inline(always)]
    fn get(self) -> usize {
        self
    }
}

/// Room for counters on the stack: as much as the other sorts of this crate keep their buffers
/// in.
pub(super) const STACK_BYTES: usize = 4096;

#[repr(C, align(16))]
pub(super) struct Stack(pub(super) [MaybeUninit<u8>; STACK_BYTES]);

/// Returns `len` zeroed counters: in `stack` if they fit, and otherwise in `heap`, allocated.
#[inline(always)]
pub(super) fn counters<'a, C: Count>(
    len: usize,
    stack: &'a mut Stack,
    heap: &'a mut Vec<C>,
) -> &'a mut [C] {
    if len <= STACK_BYTES / mem::size_of::<C>() {
        let p = stack.0.as_mut_ptr().cast::<C>();
        // SAFETY: the stack has room for `len` counters and is aligned for them (`C` is `u32`
        // or `usize`), and all-zero bytes are a valid zero.
        unsafe {
            ptr::write_bytes(p, 0, len);
            slice::from_raw_parts_mut(p, len)
        }
    } else {
        *heap = vec![C::ZERO; len];
        heap
    }
}

/// Returns room for `len` keys: in `stack` if they fit, and otherwise in `heap`, allocated.
#[inline(always)]
pub(super) fn key_slots<'a, K: Copy>(
    len: usize,
    stack: &'a mut Stack,
    heap: &'a mut Vec<K>,
) -> &'a mut [MaybeUninit<K>] {
    const { assert!(mem::align_of::<K>() <= mem::align_of::<Stack>()) };
    if len <= STACK_BYTES / mem::size_of::<K>().max(1) {
        // SAFETY: the stack has room for `len` keys and is aligned for them.
        unsafe { slice::from_raw_parts_mut(stack.0.as_mut_ptr().cast(), len) }
    } else {
        // Its length stays 0: the keys are `Copy`, and nothing reads them through it.
        *heap = Vec::with_capacity(len);
        &mut heap.spare_capacity_mut()[..len]
    }
}

/// Counts the values of `arr` into eight tables, one value after the other into the next
/// table, while the range has at most this many values, so that the eight fit in the
/// processor's fastest cache...
const TABLES_MAX_RANGE: usize = 2048;

/// ...and the slice has at least this many elements per value, so that clearing and adding up
/// the tables costs little.
const TABLES_MIN_PER_VALUE: usize = 16;

const TABLES: usize = 8;

/// The counts are rewritten into the slice by a loop that skips empty blocks of counts when the
/// range has at least this many values per element.
const SPARSE_PER_ELEMENT: usize = 32;

/// Counts the values of `arr`, all within the `k` values from `min`, and rewrites `arr` from
/// the counts.
///
/// Never inlined: with its counts on the stack, it made the frame of [`counting`] large enough
/// to be probed on every call, which cost sorted input of 100 elements 1.5 times as long.
#[inline(never)]
pub(super) fn rewrite<T: IntegerKey, C: Count>(arr: &mut [T], min: T, k: usize) {
    let len = arr.len();
    let tables = if k <= TABLES_MAX_RANGE && len >= TABLES_MIN_PER_VALUE * k {
        TABLES
    } else {
        1
    };
    let mut stack = Stack([MaybeUninit::uninit(); STACK_BYTES]);
    let mut heap = Vec::new();
    let counts = counters::<C>(tables * k, &mut stack, &mut heap);
    if tables == TABLES {
        count::<T, C, TABLES>(arr, min, counts, k);
    } else {
        count::<T, C, 1>(arr, min, counts, k);
    }
    let counts = &counts[..k];
    if k >= SPARSE_PER_ELEMENT.saturating_mul(len) {
        write_sparse(arr, min, counts);
    } else if mem::size_of::<T>() <= 2 {
        write_ahead::<T, C, 8>(arr, min, counts);
    } else {
        write_ahead::<T, C, 4>(arr, min, counts);
    }
}

/// Counts the values of `v`, all within the `k` values from `min`, into `N` tables of `k`
/// counters, value `i` into table `i mod N`, and adds them up into the first. `N` divides 8.
///
/// A count depends on the one before it: with one table, a run of equal values waits for each
/// increment to reach memory before the next can read it. With `N` tables, `N` such chains run
/// at once.
///
/// The slice is walked 8 elements at a time whatever `N` is: left to the compiler, the loop for
/// one table was not unrolled, and counted 1.4 times slower.
#[inline(always)]
fn count<T: IntegerKey, C: Count, const N: usize>(v: &[T], min: T, counts: &mut [C], k: usize) {
    const STEP: usize = 8;
    debug_assert!(STEP.is_multiple_of(N) && counts.len() == N * k);
    let c = counts.as_mut_ptr();
    if N == 1 && mem::size_of::<C>() == 2 {
        // SAFETY: as below.
        return unsafe { by_quarters(v, min, c) };
    }
    if N == 1 && v.len() >= QUARTERS_MIN_LEN && in_order_at_first(v) {
        return count_by_quarters(v, min, counts);
    }
    let (chunks, rest) = v.as_chunks::<STEP>();
    for chunk in chunks {
        for (j, x) in chunk.iter().enumerate() {
            // SAFETY: `min <= x <= max`, so `x.offset(min) < k` and the counter is in table
            // `j mod N < N`.
            unsafe { bump(c.add(j % N * k + x.offset(min))) };
        }
    }
    for x in rest {
        // SAFETY: as above, in table 0.
        unsafe { bump(c.add(x.offset(min))) };
    }
    if N > 1 {
        let (first, rest) = counts.split_at_mut(k);
        for table in rest.chunks_exact(k) {
            for (sum, &c) in first.iter_mut().zip(table) {
                *sum = sum.add(c.get());
            }
        }
    }
}

/// Turns `counts` into the sums of the counts before each: the place where the elements of
/// each counter begin.
///
/// The counts are read four at a time and summed among themselves before the sum of those
/// before them is added: one addition per four counts waits for the one before it, where a
/// running sum waits for every count.
#[inline(always)]
pub(super) fn exclusive_scan<C: Count>(counts: &mut [C]) {
    let mut sum = 0;
    let (chunks, rest) = counts.as_chunks_mut::<4>();
    for chunk in chunks {
        let [a, b, c, d] = chunk.map(|c| c.get());
        let (ab, abc) = (a + b, a + b + c);
        *chunk = [sum, sum + a, sum + ab, sum + abc].map(|s| C::ZERO.add(s));
        sum += abc + d;
    }
    for c in rest {
        let count = c.get();
        *c = C::ZERO.add(sum);
        sum += count;
    }
}

/// The places four keys in a row take, from their counters `b` and the next free place `next`
/// of each counter before them: a key takes the place after those taken by the keys before it
/// with the same counter.
///
/// The four next places are all read before any is written back, so a run of keys with one
/// counter waits for memory once per four keys, not once per key.
#[inline(always)]
pub(super) fn places4(b: [usize; 4], next: [usize; 4]) -> [usize; 4] {
    [
        next[0],
        next[1] + usize::from(b[1] == b[0]),
        next[2] + usize::from(b[2] == b[0]) + usize::from(b[2] == b[1]),
        next[3] + usize::from(b[3] == b[0]) + usize::from(b[3] == b[1]) + usize::from(b[3] == b[2]),
    ]
}

/// One table of `u32` or `usize` counts is walked as four quarters side by side, for slices of
/// at least this many elements whose first values are mostly in order, by [`count_by_quarters`];
/// one of `u16` counts always, by [`by_quarters`].
const QUARTERS_MIN_LEN: usize = 1024;

/// [`by_quarters`] out of line: inlined into [`rewrite`] next to the plain loop, it made that
/// loop count `char`s 1.2 times slower from 100,000 elements on.
#[inline(never)]
fn count_by_quarters<T: IntegerKey, C: Count>(v: &[T], min: T, counts: &mut [C]) {
    // SAFETY: `counts` holds a counter for every value of `v`.
    unsafe { by_quarters(v, min, counts.as_mut_ptr()) }
}

/// Counts the values of `v` from `min` into the counters at `c`, walking `v` as four quarters
/// side by side: counts do not depend on the order of the values, and a run of equal values
/// then does not wait on each increment (2.2 times faster on nearly sorted input with sixteen
/// of each value). On random values with `u32` counts, the four streams cost 1.02–1.07 times as
/// long as one; with `u16` counts, the plain loop cost 1.1–1.2 times as long as four streams.
///
/// # Safety
///
/// `c` must hold a counter for every value of `v`, `x.offset(min)` for each.
#[inline(always)]
unsafe fn by_quarters<T: IntegerKey, C: Count>(v: &[T], min: T, c: *mut C) {
    let quarter = v.len() / 4;
    let (a, rest) = v.split_at(quarter);
    let (b, rest) = rest.split_at(quarter);
    let (d, rest) = rest.split_at(quarter);
    let (e, rest) = rest.split_at(quarter);
    for (((a, b), d), e) in a.iter().zip(b).zip(d).zip(e) {
        for x in [a, b, d, e] {
            // SAFETY: guaranteed by the caller.
            unsafe { bump(c.add(x.offset(min))) };
        }
    }
    for x in rest {
        // SAFETY: as above.
        unsafe { bump(c.add(x.offset(min))) };
    }
}

/// Increments the counter at `c` and returns its value before.
///
/// # Safety
///
/// `c` must be valid for reads and writes.
#[inline(always)]
pub(super) unsafe fn bump<C: Count>(c: *mut C) -> usize {
    // SAFETY: guaranteed by the caller.
    unsafe {
        let before = *c;
        *c = before.add(1);
        before.get()
    }
}

/// Rewrites `v` from `counts`, `counts[o]` copies of `min + o` after each other.
///
/// Every value is first written `W` times without looking at its count, and only a count
/// greater than `W` takes a branch. Whatever was written beyond the count is overwritten by the
/// values after it. Branching on every count instead mispredicts on a range of about as many
/// values as elements, where counts of 0, 1 and 2 are all common.
#[inline(always)]
fn write_ahead<T: IntegerKey, C: Count, const W: usize>(v: &mut [T], min: T, counts: &[C]) {
    let len = v.len();
    let base = v.as_mut_ptr();
    let mut pos = 0;
    let mut o = 0;
    while o < counts.len() && pos + W <= len {
        let c = counts[o].get();
        let x = T::nth(min, o);
        // SAFETY: `pos + W <= len`, and the counts add up to `len`, so `pos + c <= len`.
        unsafe {
            for j in 0..W {
                base.add(pos + j).write(x);
            }
            if c > W {
                slice::from_raw_parts_mut(base.add(pos + W), c - W).fill(x);
            }
        }
        pos += c;
        o += 1;
    }
    for (o, &c) in counts.iter().enumerate().skip(o) {
        let c = c.get();
        v[pos..pos + c].fill(T::nth(min, o));
        pos += c;
    }
}

/// Rewrites `v` from `counts` like [`write_ahead`], for a range with many more values than
/// elements: blocks of 8 empty counts are skipped with one test.
#[inline(always)]
fn write_sparse<T: IntegerKey, C: Count>(v: &mut [T], min: T, counts: &[C]) {
    const BLOCK: usize = 8;
    let mut pos = 0;
    let (blocks, rest) = counts.as_chunks::<BLOCK>();
    let mut o = 0;
    for block in blocks {
        // Not `any`, which stops at the first nonzero count and is not vectorized.
        if block.iter().fold(false, |any, &c| any | (c != C::ZERO)) {
            for (j, &c) in block.iter().enumerate() {
                let c = c.get();
                v[pos..pos + c].fill(T::nth(min, o + j));
                pos += c;
            }
        }
        o += BLOCK;
    }
    for (j, &c) in rest.iter().enumerate() {
        let c = c.get();
        v[pos..pos + c].fill(T::nth(min, o + j));
        pos += c;
    }
}

/// The slice is placed as this many segments, each with its own places, while the range has
/// at most this many keys...
const SEGMENTS: usize = 8;

const SEGMENTS_MAX_RANGE: usize = 256;

/// ...and the slice has at least this many elements per key.
const SEGMENTS_MIN_PER_KEY: usize = 16;

/// Places every element of `arr` by its key in `keys`, all within the `k` keys from `min`, into
/// a buffer at the place the counts give it, and copies the buffer back.
///
/// The places are `u16` up to 65,535 elements in one segment, which halves the memory they
/// take (1.05–1.25 times faster from 1000 keys on), and `u32` with eight segments, whose loops
/// took 1.05 times as long with `u16`; `usize` beyond `u32::MAX` elements.
pub(super) fn scatter<T, K: IntegerKey>(arr: &mut [T], keys: &[K], min: K, k: usize) {
    let len = arr.len();
    let segments = k <= SEGMENTS_MAX_RANGE && len >= SEGMENTS_MIN_PER_KEY * k;
    if !segments && len <= u16::MAX as usize {
        scatter_in::<T, K, u16>(arr, keys, min, k, 1);
    } else if len <= u32::MAX as usize {
        scatter_in::<T, K, u32>(arr, keys, min, k, if segments { SEGMENTS } else { 1 });
    } else {
        scatter_in::<T, K, usize>(arr, keys, min, k, if segments { SEGMENTS } else { 1 });
    }
}

/// [`scatter`] with places of type `C`, in `segments` segments: 1 or [`SEGMENTS`].
fn scatter_in<T, K: IntegerKey, C: Count>(
    arr: &mut [T],
    keys: &[K],
    min: K,
    k: usize,
    segments: usize,
) {
    let mut stack = Stack([MaybeUninit::uninit(); STACK_BYTES]);
    let mut heap = Vec::new();
    let next = counters::<C>(segments * k, &mut stack, &mut heap);
    if segments == SEGMENTS {
        place::<T, K, C, SEGMENTS>(arr, keys, min, k, next);
    } else {
        place::<T, K, C, 1>(arr, keys, min, k, next);
    }
}

/// Splits `arr` into `S` segments, the last one taking the remainder, and stably places its
/// elements by their keys in `keys` into a buffer, then copies the buffer back.
///
/// Every segment has its own place for each key, after the places of the same key in the
/// segments before it, so the order of equal keys is kept. The segments are walked side by
/// side: placing an element waits for the place handed out before it with the same key and in
/// the same segment, and with `S` segments `S` such chains run at once.
///
/// `next` holds `S·k` zeroed counters, which become the next place of each key in each segment.
#[inline(always)]
fn place<T, K: IntegerKey, C: Count, const S: usize>(
    arr: &mut [T],
    keys: &[K],
    min: K,
    k: usize,
    next: &mut [C],
) {
    let len = arr.len();
    let seg = len / S;
    let tail = S * seg;
    let next = next.as_mut_ptr();
    let keys = keys.as_ptr();
    // Segment `s` is `arr[s·seg..(s + 1)·seg]`, and the last one also takes `arr[S·seg..]`.
    // One segment is counted as four quarters side by side, as counts do not depend on the
    // order of the keys: a run of equal keys then does not wait on each increment.
    let (quarters, quarter) = if S == 1 { (4, len / 4) } else { (S, seg) };
    for i in 0..quarter {
        for q in 0..quarters {
            // SAFETY: `q·quarter + i < quarters·quarter <= len`. Every key lies between `min`
            // and the largest key, so its offset is less than `k`, and the counter is in
            // `next`: in table `q` of `S`, or in the one table.
            unsafe {
                let t = if S == 1 { 0 } else { q };
                bump(next.add(t * k + (*keys.add(q * quarter + i)).offset(min)));
            }
        }
    }
    for i in quarters * quarter..len {
        // SAFETY: as above, in the last segment.
        unsafe { bump(next.add((S - 1) * k + (*keys.add(i)).offset(min))) };
    }
    if S == 1 {
        // SAFETY: `next` holds `S·k` counters.
        exclusive_scan(unsafe { slice::from_raw_parts_mut(next, k) });
    } else {
        let mut sum = 0;
        for o in 0..k {
            for s in 0..S {
                // SAFETY: `s·k + o < S·k`.
                unsafe {
                    let c = next.add(s * k + o);
                    let count = (*c).get();
                    *c = C::ZERO.add(sum);
                    sum += count;
                }
            }
        }
    }
    let mut buf = Buffer::<T>::new(len);
    let dst = buf.get();
    let base = arr.as_ptr();
    if S == 1 {
        // Four keys at a time: a run of equal keys waits for memory once per four keys.
        let mut i = 0;
        while i + 4 <= len {
            // SAFETY: as below, the places handed out as one key at a time would.
            unsafe {
                let b = [0, 1, 2, 3].map(|j| (*keys.add(i + j)).offset(min));
                let p = places4(b, b.map(|b| (*next.add(b)).get()));
                for j in 0..4 {
                    *next.add(b[j]) = C::ZERO.add(p[j] + 1);
                }
                for (j, &p) in p.iter().enumerate() {
                    ptr::copy_nonoverlapping(base.add(i + j), dst.add(p), 1);
                }
            }
            i += 4;
        }
        for i in i..len {
            // SAFETY: as below.
            unsafe {
                let pos = bump(next.add((*keys.add(i)).offset(min)));
                ptr::copy_nonoverlapping(base.add(i), dst.add(pos), 1);
            }
        }
        // SAFETY: as below.
        unsafe { ptr::copy_nonoverlapping(dst, arr.as_mut_ptr(), len) };
        return;
    }
    for i in 0..seg {
        for s in 0..S {
            // SAFETY: as in the count above. The keys are the ones counted, so the places of
            // each key in each segment are handed out exactly once each, and all lie below
            // `len`.
            unsafe {
                let j = s * seg + i;
                let pos = bump(next.add(s * k + (*keys.add(j)).offset(min)));
                ptr::copy_nonoverlapping(base.add(j), dst.add(pos), 1);
            }
        }
    }
    for i in tail..len {
        // SAFETY: as above, in the last segment.
        unsafe {
            let pos = bump(next.add((S - 1) * k + (*keys.add(i)).offset(min)));
            ptr::copy_nonoverlapping(base.add(i), dst.add(pos), 1);
        }
    }
    // SAFETY: the `len` places hold each element of `arr` exactly once, and `dst` does not
    // overlap `arr`.
    unsafe { ptr::copy_nonoverlapping(dst, arr.as_mut_ptr(), len) };
}