A

The A Library is a set of algorithms.

Table of contents

• A
  • Table of contents
  • Sorting
    • Bubble
      • Examples
      • Efficiency
    • Selection
      • Examples
      • Efficiency
    • Insertion
      • Examples
      • Efficiency
    • Cocktail Shaker
      • Examples
      • Efficiency
    • Gnome
      • Examples
      • Efficiency
    • Comb
      • Examples
      • Efficiency
    • Merge
      • Examples
      • Efficiency
    • Quick
      • Examples
      • Efficiency
    • Heap
      • Examples
      • Efficiency
    • Tim
      • Examples
      • Efficiency
    • Intro
      • Examples
      • Efficiency
    • Shell
      • Examples
      • Efficiency
    • Drift
      • Examples
      • Efficiency
    • Counting
      • Examples
      • Efficiency
    • Radix
      • Examples
      • Efficiency
    • Bucket
      • Examples
      • Efficiency
    • Pigeonhole
      • Examples
      • Efficiency
    • Tree
      • Examples
      • Efficiency
    • Cycle
      • Examples
      • Efficiency
    • Bitonic
      • Examples
      • Efficiency
    • Odd-Even
      • Examples
      • Efficiency
    • Stooge
      • Examples
      • Efficiency
    • Sleep
      • Examples
      • Efficiency

Sorting

Bubble

Bubble sort is a simple, stable, in-place sorting algorithm. It repeatedly scans the slice, swapping adjacent elements that are out of order. This implementation uses these optimizations:

• Early exit: stop when a pass performs no swaps (already sorted).
• Last-swap bound: the next pass only scans up to the last index that swapped (the tail is already sorted).
• Hole shifting: an element travelling k slots is read once, the k elements it overtakes shift one slot each, and it is written once: k + 1 moves instead of the 3k of k swaps.
• Branchless passes for small elements (at most 8 bytes, no drop glue): the running maximum is held in a register and every comparison writes the smaller element into the slot behind it, with no branch on the outcome, and two consecutive passes run at once, the second trailing the first, so that their comparisons overlap. Each pass picks branchy or branchless from what the previous one found, so sorted input still costs one branchy pass. The comparisons and their outcomes are exactly those of classic bubble sort; on random u64 and u32 input this is 1.2–2.9 times faster, and up to 3.3 times on elements that are each a few slots from their places.

Examples

Rust usage with integers:

use a::sort::bubble;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8];
  bubble(&mut v);
  assert_eq!(v, vec![1, 2, 4, 5, 8]);
}

Sorting strings:

use a::sort::bubble;

fn main() {
  let mut fruits = vec!["pear", "apple", "banana", "apple"]; 
  bubble(&mut fruits);
  assert_eq!(fruits, vec!["apple", "apple", "banana", "pear"]);
}

Efficiency

• Time complexity:
  • Worst: O(n^2)
  • Average: O(n^2)
  • Best: O(n) with early-exit when input is already sorted
• Comparisons and swaps (tight bounds for the canonical variant):
  • Worst comparisons: n(n−1)/2; worst swaps: n(n−1)/2
  • Best comparisons: n−1; best swaps: 0
• Space complexity: O(1) extra (in-place)
• Stability: stable (equal elements keep their relative order)
• Adaptivity: good for nearly-sorted data due to early exit and last-swap bound; unsuitable for large, random inputs compared to O(n log n) sorts

Selection

Selection sort is a simple, in-place, unstable sorting algorithm. Each pass selects the extremes of the unsorted part of the slice and moves them to their final positions. This implementation is double-ended and uses three optimizations:

• Pairwise min-max scan: elements are taken two at a time, compared with each other, and only the smaller one is compared with the running minimum and the larger one with the running maximum, for ⌈3m/2⌉ − 2 comparisons per pass over m elements (the fewest possible for finding both extremes) instead of 2m − 2.
• Duplicate gathering: every comparison is three-way, so all copies of the minimum and maximum keys are placed in the same pass at no extra comparisons; input with k distinct keys finishes in at most ⌈k/2⌉ passes, and a range found to be all equal ends the sort.
• Lazy placement: an extreme with no duplicates is only remembered by index and moved once the pass is over, so distinct keys cost at most n − 1 swaps and already sorted input is never moved.

The scan picks which element of a pair to compare with each extreme without a branch, since which one is smaller is a coin flip on random input; with the same comparisons, random input with distinct keys sorts 1.7–2.5 times faster from 1,000 elements up. For elements of 9 to 32 bytes (strings, for one), whose comparisons are slow to start, the first pass counts how predictable the pairs are and later passes branch when they are.

Examples

Rust usage with integers:

use a::sort::selection;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8];
  selection(&mut v);
  assert_eq!(v, vec![1, 2, 4, 5, 8]);
}

Many duplicates (three distinct keys, sorted in two passes):

use a::sort::selection;

fn main() {
  let mut v = vec![3, 1, 2, 3, 1, 2, 2, 1];
  selection(&mut v);
  assert_eq!(v, vec![1, 1, 1, 2, 2, 2, 3, 3]);
}

Efficiency

• Time complexity:
  • Worst: O(n^2), when all keys are distinct
  • Average: O(n^2) for distinct keys; O(nk) with k distinct keys
  • Best: O(n), when all elements are equal
• Comparisons and swaps:
  • Worst comparisons: n(3n−2)/8 for even n, 3(n²−1)/8 for odd n (about 25% fewer than the n(n−1)/2 of classic selection sort); swaps with distinct keys: at most n−1
  • Best comparisons: n−1 (all equal); best swaps: 0 (already non-decreasing input)
  • With repeated keys: at most 2m swaps per pass over m elements, trading the n−1 swap bound for far fewer comparisons and passes
• Space complexity: O(1) extra (in-place)
• Stability: unstable (equal elements may be reordered)
• Adaptivity: not adaptive to existing order (sorted input with distinct keys costs as much as any other), but adaptive to duplicates: the fewer distinct keys, the fewer passes; unsuitable for large inputs compared to O(n log n) sorts

Insertion

Insertion sort is a simple, stable, in-place sorting algorithm. It grows a sorted prefix from the left, inserting each new element after every prefix element that is not greater than it. This implementation is a pair insertion sort (the variant Java's dual-pivot quicksort uses for short ranges) with three optimizations:

• Sorted fast path: the smaller element of each new pair is first compared with the last element of the prefix; if it is not smaller, the pair is already in place, so sorted input costs exactly n−1 comparisons.
• Galloping search: an insertion point is found by probing 1, 2, 4, 8, … slots to the left and then binary searching the last gap, so an element that moves d slots costs at most 2⌊log₂ d⌋ + 2 comparisons instead of d.
• Pair moves: two elements are inserted at once; the smaller one is only searched for left of the larger one's slot, and prefix elements greater than both shift right by two slots in a single move, so they move once instead of twice. Short moves of elements of up to 32 bytes are made in place, four elements at a time, instead of through memmove, which costs them more than the copying (1.05–1.3 times faster for integers on short or nearly sorted slices and up to 1.5 times on short reverse-sorted ones, within 1.03 times either way on long random ones).

Examples

Rust usage with integers:

use a::sort::insertion;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8];
  insertion(&mut v);
  assert_eq!(v, vec![1, 2, 4, 5, 8]);
}

Equal keys keep their original order (cards are compared by rank only):

use a::sort::insertion;
use std::cmp::Ordering;

#[derive(Debug, PartialEq, Eq)]
struct Card(u8, char);

impl Ord for Card {
  fn cmp(&self, other: &Self) -> Ordering {
    self.0.cmp(&other.0)
  }
}

impl PartialOrd for Card {
  fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    Some(self.cmp(other))
  }
}

fn main() {
  let mut cards = vec![Card(2, 'a'), Card(1, 'x'), Card(2, 'b'), Card(0, 'y')];
  insertion(&mut cards);
  assert_eq!(cards, vec![Card(0, 'y'), Card(1, 'x'), Card(2, 'a'), Card(2, 'b')]);
}

Efficiency

• Time complexity:
  • Worst: O(n^2) element moves, but only O(n log n) comparisons
  • Average: O(n^2) moves, O(n log n) comparisons
  • Best: O(n), when the input is already sorted
• Comparisons and moves (dₓ = how many slots element x moves left, I = Σ dₓ = number of inversions):
  • Any input: at most n−1 + Σ 2⌈log₂(dₓ+1)⌉ comparisons and at most I + n moves
  • Worst comparisons: at most 2n·log₂ n (17,020 for n = 1000, against 499,500 for classic insertion sort)
  • Reverse sorted: about (n/2)·log₂ n + n comparisons and n²/4 moves
  • Best comparisons: n−1; best moves: 0
  • Against inserting one element at a time with the same search: about a third fewer moves on random input and half on reverse-sorted input
• Space complexity: O(1) extra (in-place)
• Stability: stable (equal elements keep their relative order)
• Adaptivity: very good; cost grows with the logarithm of how far elements move, so nearly-sorted input sorts in close to linear time; unsuitable for large, random inputs compared to O(n log n) sorts because of the O(n^2) moves

Cocktail Shaker

Cocktail shaker sort is a simple, stable, in-place sorting algorithm: bubble sort that alternates direction. A forward pass carries the largest element seen so far towards the end, then a backward pass carries the smallest element seen so far towards the front, so the unsorted range shrinks from both ends. Unlike bubble sort, a small element near the end (a "turtle") reaches its place in a single backward pass instead of moving one slot per pass. This implementation uses three optimizations:

• Last-move bounds at both ends: a forward pass ends the unsorted range at the last element it moved and a backward pass starts it just after the last element it moved, so sorted runs at either end are never rescanned; a pass that moves nothing ends the sort.
• Hole shifting instead of swapping: an element travelling k slots is read once, the k elements it overtakes shift one slot each as they are compared with it, and it is written once into its final slot: k + 1 moves instead of the 3k of k swaps. Shifting while comparing touches each element once and avoids a memmove call per (mostly very short) carry, which makes it about twice as fast on random integers as finding the distance first and moving a block afterwards.
• Branchless passes for small elements (at most 8 bytes, no drop glue): the running extreme is held in a register and every comparison writes the other element into the slot behind it, with no branch on the outcome. Each pass picks branchy or branchless from what the previous one found, so sorted input still costs one branchy pass. The comparisons are exactly those of classic cocktail shaker sort; on random u64 input this is 1.8–2.6 times faster up to a few hundred elements and 1.2 times at 1,000, and 1.5–2.6 times on elements that are each a few slots from their places.

Examples

Rust usage with integers:

use a::sort::cocktail_shaker;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8];
  cocktail_shaker(&mut v);
  assert_eq!(v, vec![1, 2, 4, 5, 8]);
}

A turtle (the 0 at the end reaches the front in one backward pass; bubble sort would need five passes):

use a::sort::cocktail_shaker;

fn main() {
  let mut v = vec![1, 2, 3, 4, 5, 0];
  cocktail_shaker(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5]);
}

Efficiency

• Time complexity:
  • Worst: O(n^2)
  • Average: O(n^2)
  • Best: O(n) with early-exit when input is already sorted
• Comparisons and moves (I = number of inversions, C = number of carries, i.e. elements picked up and moved at least one slot, counted once per pass):
  • Worst comparisons: n(n−1)/2 (reverse sorted); worst moves: n(n+1)/2 − 1
  • Any input: at most n(n−1)/2 comparisons and exactly I + C ≤ 2I moves
  • Best comparisons: n−1; best moves: 0
  • Random input: about n²/3 comparisons, a third fewer than bubble sort's n²/2 (≈ 332,000 against ≈ 496,000 for n = 1000)
  • Turtle [1, 2, …, n−1, 0]: 3n−6 comparisons, against n(n−1)/2 for bubble sort (2,994 against 499,500 for n = 1000)
• Space complexity: O(1) extra (in-place)
• Stability: stable (equal elements keep their relative order)
• Adaptivity: good for nearly-sorted data, including elements that are out of place in either direction; unsuitable for large, random inputs compared to O(n log n) sorts

Gnome

Gnome sort is a simple, stable, in-place sorting algorithm. A gnome walks along the slice comparing each element with the one before it: while they are in order it steps forward, and when they are not it carries the element back, one slot at a time, until it meets an element that is not greater than it or reaches the front. The slice behind the gnome is always sorted. This implementation uses two optimizations:

• Teleportation: classic gnome sort walks forward again over the slots it just carried an element back across, re-comparing pairs it already knows are in order; this gnome returns to where it turned back at once. Every comparison it makes is one classic gnome sort also makes, in the same order, but it saves exactly one per inversion: about half of them on random input.
• Hole shifting instead of swapping: an element travelling d slots is read once, the d greater elements it passes shift right by one slot each as they are compared with it, and it is written once into its final slot: d + 1 moves instead of the 3d of d swaps. The walk back is unrolled four times, which makes small elements up to 1.2 times faster (reverse-sorted input up to 1.5 times).

With both optimizations gnome sort makes the same comparisons and moves as insertion sort with a linear search; the Insertion sort above uses a galloping search instead and makes far fewer comparisons.

Examples

Rust usage with integers:

use a::sort::gnome;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8];
  gnome(&mut v);
  assert_eq!(v, vec![1, 2, 4, 5, 8]);
}

A turtle (the 0 at the end is carried to the front in a single walk back):

use a::sort::gnome;

fn main() {
  let mut v = vec![1, 2, 3, 4, 5, 0];
  gnome(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5]);
}

Efficiency

• Time complexity:
  • Worst: O(n^2)
  • Average: O(n^2)
  • Best: O(n), when the input is already sorted
• Comparisons and moves (I = number of inversions, C = number of elements that move, F = number of elements other than the first that are smaller than everything before them, i.e. carried all the way to the front):
  • Any input: exactly n−1 + I − F comparisons and exactly I + C moves
  • Worst comparisons: n(n−1)/2 (reverse sorted), against n(n−1) for classic gnome sort; worst moves: n(n+1)/2 − 1
  • Best comparisons: n−1; best moves: 0
  • Random input: about n²/4 comparisons and n²/4 moves, against n²/2 comparisons and n²/4 swaps (3n²/4 moves) for classic gnome sort (≈ 250,800 against ≈ 500,600 comparisons for n = 1000)
  • Turtle [1, 2, …, n−1, 0]: 2n−3 comparisons, against 3n−4 for classic gnome sort and n(n−1)/2 for bubble sort
• Space complexity: O(1) extra (in-place)
• Stability: stable (equal elements keep their relative order)
• Adaptivity: good for nearly-sorted data; cost grows with the number of inversions; unsuitable for large, random inputs compared to O(n log n) sorts

Comb

Comb sort is a simple, unstable, in-place sorting algorithm: bubble sort with a gap. A pass compares every element with the one gap slots after it and swaps the two if they are out of order, so a small element near the end (a "turtle") moves gap slots left in one step instead of one. The gap starts at the length of the slice and shrinks by a factor of 1.3 after each pass; once it reaches 1, the slice is nearly sorted and bubble sort finishes it. This implementation uses four optimizations:

• Rule of 11 (Combsort11): a gap of 9 or 10 is replaced by 11, which leaves fewer turtles for the final bubble sort; on random input of 10,000 elements this saves about 6% of the comparisons and narrows their spread.
• Adaptive finish: the final phase is this crate's Bubble sort, which scans only up to the last element it moved and moves elements by hole shifting, instead of the repeated full passes of classic comb sort.
• Branchless swaps for small elements: whether a gapped pass swaps a pair is close to a coin flip, which defeats the branch predictor, so for elements of at most 32 bytes both slots are rewritten from addresses chosen by the comparison, and each pass is walked in blocks of gap pairs over two non-overlapping slices. On random input this is 3–4.5 times faster for integers and 1.5–1.8 times for strings. Larger elements are swapped only when needed, since rewriting them costs more than a misprediction.
• Carrying in registers at small gaps, for elements of at most 16 bytes: at a gap of 14 or less, each pair overlaps the one gap slots before it, so a swap has to reach memory before the next comparison can read it back. Instead, the pass holds the largest element seen so far of every chain c, c + gap, c + 2·gap, … in a register, one per chain, and writes back only the smaller of it and the next element: the comparisons of a plain pass, in its order and with the same outcomes and result, with one move per swap plus one per carried element instead of two per swap, and the gap chains overlapping. Together with the faster final bubble sort this makes the whole sort 1.15–1.5 times faster for u64, 1.4–1.8 times for u32 and 1.2–1.5 times for pairs of integers than before; String, whose comparisons usually read memory, keeps the plain pass.

Examples

Rust usage with integers:

use a::sort::comb;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8];
  comb(&mut v);
  assert_eq!(v, vec![1, 2, 4, 5, 8]);
}

Turtles (the small elements at the end move many slots per step):

use a::sort::comb;

fn main() {
  let mut v = vec![5, 6, 7, 8, 9, 0, 1, 2, 3, 4];
  comb(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

Efficiency

• Time complexity:
  • Worst: O(n^2) in theory (no known input reaches it in practice, but no O(n log n) bound has been proved)
  • Average: about n·log₁.₃ n comparisons
  • Best: O(n log n); the gapped passes cost the same on every input
• Comparisons (g₁ > g₂ > … > gₖ ≥ 2 = the gaps, k ≈ log₁.₃ n − 4):
  • Gapped passes: exactly Σ (n − gᵢ) ≈ n·(log₁.₃ n − 7.3) on every input
  • Best (already sorted): Σ (n − gᵢ) + n − 1 (19,706 for n = 1000); best moves: 0
  • Random input: about n·(log₁.₃ n − 4.5) (≈ 21,300 for n = 1000, against ≈ 499,000 for bubble sort and ≈ 22,500 for classic comb sort without the rule of 11 and the adaptive finish)
• Space complexity: O(1) extra (in-place)
• Stability: unstable (a gapped swap can carry an element past an equal one)
• Adaptivity: not adaptive (only the final bubble sort gets cheaper on nearly-sorted input); much faster than the other quadratic sorts here on random input, about 1.5 times faster than slice::sort_unstable on 10,000 random u32 and about as fast on u64 (1.2 times slower at 1,000,000)

Merge

Merge sort is a stable, O(n log n) sorting algorithm that uses a buffer. It splits the slice into two halves, sorts each half recursively, and merges the two sorted halves into one. Every element takes part in one merge per level of recursion and there are about log₂ n levels, so the cost hardly depends on the input. This implementation uses a buffer of n elements, kept on the stack when it fits in 4 KiB and allocated once otherwise, and seven optimizations:

• Short runs sorted without branches: halves of at most 8 elements are not split further. A run is first scanned for order, which leaves a sorted run alone after len−1 comparisons and otherwise stops at the first descent, usually after one or two; then its two halves of at most 4 elements are sorted straight into the buffer by fixed sequences of comparisons that select where each element goes instead of branching on the outcome (1, 3 and 5 comparisons for 2, 3 and 4 elements, the last being the standard library's stable four-element sort), and merged back. Short runs took up to 60% of the time when they were insertion sorted; together with the stack buffer below, this makes the whole sort 1.2–2.8 times faster for integers (most for small slices) and 1.02–1.9 times for strings and large elements.
• Short slices of small elements noted for order: for elements of at most 8 bytes, a half of up to 64 elements is first scanned for descents (elements smaller than the one before) with one comparison per element and no branch on the answers. None and it is left alone, one at every element and it is reversed, otherwise runs and stretches of the recursion without a descent are left alone and the rest is sorted as above (random integers 1.1 times faster for about n more comparisons, sorted input 3.3–4 times, reverse-sorted 2.8–8 times).
• Ordered halves are not merged: if the first element of the right half is not smaller than the last element of the left half, one comparison replaces the merge, so already-sorted input costs exactly n−1 comparisons and is never moved.
• Reversed halves are swapped: if the last element of the right half is smaller than the first element of the left half, the halves trade places as blocks with no further comparison, so reverse-sorted input costs about 2.6n comparisons instead of n·log₂ n (about n for elements of at most 8 bytes).
• No level copied out before it is merged: every merge reads its halves where the level below left them, in the slice or in the buffer, and writes the other place, so each level moves every element once instead of twice, and the result is copied back at most once (1.03–1.1 times faster for integers and strings on random input, 1.06–1.45 times for 64-byte elements).
• Bidirectional, branchless merging: each merge proceeds from both ends at once, the front taking the smaller of the two first elements and the back the larger of the two last ones. The two independent chains of comparisons overlap in the processor, and every step copies from an address chosen by the comparison instead of branching on it. On random input this is 1.2–1.6 times faster than the classic merge that copies only the left half out and merges from the front.
• Long merges split in two or four: a merge of 128 elements or more is split at the middle of its result by a binary search (co-ranking) into two independent merges from both ends, four chains the processor overlaps, and from 4096 elements of at most 32 bytes into four; each part stops when a half has at most one element left, so it never compares an element whose copy is written already (1.13–1.4 times faster for integers, 1.12–1.55 times for strings and 1.08–1.2 times for 64-byte elements from 1000 elements on).
• No allocation for small slices: a buffer of up to 4 KiB lives on the stack, so a slice that fits in it (512 u64s, say) is sorted without touching the allocator.

Examples

Rust usage with integers:

use a::sort::merge;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
  merge(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

Equal keys keep their original order (cards are compared by rank only):

use a::sort::merge;
use std::cmp::Ordering;

#[derive(Debug, PartialEq, Eq)]
struct Card(u8, char);

impl Ord for Card {
  fn cmp(&self, other: &Self) -> Ordering {
    self.0.cmp(&other.0)
  }
}

impl PartialOrd for Card {
  fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    Some(self.cmp(other))
  }
}

fn main() {
  let ranks = [3, 1, 3, 0, 1, 3, 0, 2, 1, 0];
  let mut cards: Vec<Card> = "abcdefghij".chars().zip(ranks).map(|(c, r)| Card(r, c)).collect();
  merge(&mut cards);
  let order: String = cards.iter().map(|c| c.1).collect();
  assert_eq!(order, "dgjbeihacf");
}

Efficiency

• Time complexity:
  • Worst: O(n log n)
  • Average: O(n log n)
  • Best: O(n), when the input is already sorted (or made of ordered or reversed halves at every level)
• Comparisons and moves (a merge of m elements makes at most 2⌊m/2⌋ comparisons after the two checks, fewer when a half runs out early, plus about 3·log₂ m for the binary searches of a split merge, and moves every element once, from where its halves are to the other place):
  • Best (already sorted): n−1 comparisons, 0 moves
  • Reverse sorted: about 2.6n comparisons (2,590 for n = 1000, against 5,044 for the textbook merge sort; about n for elements of at most 8 bytes, 1,010 for n = 1000)
  • Random input: about n·log₂ n − 0.35n comparisons (≈ 9,570 for n = 1000; ≈ 10,290 for elements of at most 8 bytes, the scans for descents included; the textbook merge sort makes ≈ 8,700, since the checks cost a comparison or two per merge and a bidirectional merge does not stop when one half runs out) and about n·log₂(n/8) + 2n moves
  • Worst: at most n·log₂ n + O(n) comparisons and 1.5n·⌈log₂(n/8)⌉ + 3n moves
• Space complexity: O(n) extra (one buffer of n elements, on the stack up to 4 KiB, otherwise allocated once) plus O(log n) stack
• Stability: stable (equal elements keep their relative order)
• Adaptivity: adaptive at the scale of runs and halves (sorted and reverse-sorted input are nearly linear). Against slice::sort, with new input for every sort: 1.6–2.4 times faster on up to 64 random integers and 1.08–1.23 times slower from 1000 on, 1.07–1.09 times slower on random strings of 1000 to 100,000 (1.65 times faster on a million), 1.1–1.35 times faster on random 64-byte elements from 1000 on and 1.2–2.6 times on nearly sorted integers, but 3–6 times slower with few distinct keys and 1.6–10 times on reverse-sorted input from 1000 elements on, which the standard library's stable sort handles in one pass

Quick

Quick sort is an unstable, in-place, O(n log n) sorting algorithm. It picks a pivot, partitions the slice into the elements smaller than the pivot and the rest, puts the pivot between them, and sorts the two parts the same way. This implementation uses seven optimizations:

• Sorted and reverse-sorted input is recognised: the slice is first scanned for one ascending or strictly descending run; if it covers the whole slice, the slice is left alone or reversed, at n−1 comparisons (usually two or three on other input).
• Pivots from a median of samples: the median of three elements spread over the slice, from 64 elements on the median of three such medians (the "ninther"), and from 4096 elements on a pseudo-median of 27 evenly spaced samples, three times as many for every 16 times the length, which keeps comparisons at about n·log₂ n on random input, against 1.39·n·log₂ n for a random pivot.
• Branchless partitioning for elements of at most 64 bytes: whether an element is smaller than the pivot is a coin flip on random input, so instead of branching, a vacant slot cycles through the slice and every element is moved unconditionally, the comparison only choosing where (Lomuto's scheme, made branchless). That is 1.9–4.3 times faster than Hoare's scheme for integers and 1.4–2.5 times for strings; larger elements, for which two moves per element cost more than a misprediction, use Hoare's scheme, which moves only misplaced pairs (two moves per pair, cycled through a vacant slot, instead of three for a swap).
• Runs of equal elements in one pass: if the pivot equals the pivot of the enclosing partition, the part is split into the elements equal to it, which are done, and the rest, so k distinct keys cost O(n log k) and all-equal input is never quadratic.
• Recursion into the smaller part only, looping on the larger one, so the stack never holds more than log₂ n frames.
• Sorting networks for short parts: for elements of at most 16 bytes, parts of at most 8 elements are sorted by optimal sorting networks made of branchless compare-exchanges, unrolled for each length so the elements stay in registers (1.3–1.85 times faster than insertion sort for random integers); larger elements, for which a compare-exchange's three moves cost more, sort parts of at most 16 elements by insertion sort.
• A guaranteed O(n log n): a part still being partitioned after 2·log₂ n levels means the pivots were consistently bad, which an adversary that answers comparisons adaptively can force on any pivot rule; such a part is finished by heap sort (the "introsort" idea). Against McIlroy's adversary, 10,000 elements cost about 480,000 comparisons instead of 8.4 million.

Examples

Rust usage with integers:

use a::sort::quick;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
  quick(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

Many duplicates (each distinct pivot takes all its copies out in one pass):

use a::sort::quick;

fn main() {
  let mut v: Vec<u8> = (0..1000).map(|i| (i * 7 % 3) as u8).collect();
  quick(&mut v);
  assert!(v.windows(2).all(|w| w[0] <= w[1]));
}

Efficiency

• Time complexity:
  • Worst: O(n log n), thanks to the Heap sort fallback
  • Average: O(n log n)
  • Best: O(n), when the input is sorted, reverse sorted or all equal
• Comparisons:
  • Best (sorted, reverse sorted, all equal): n−1
  • Random input: about n·log₂ n + 0.2n to n·log₂ n + 0.6n (≈ 10,200 for n = 1000, n·log₂ n + 0.6n for n = 100,000 and 1,000,000), up to 0.4n more for elements larger than 16 bytes
  • k distinct keys: O(n log k), about 1.1–1.45·n·(log₂ k + 1) in practice
• Space complexity: O(log n) stack, no allocation (in-place)
• Stability: unstable (equal elements may be reordered)
• Adaptivity: adaptive to sorted and reverse-sorted input and to repeated keys; on nearly sorted input (a few elements out of place) Hoare's scheme would be 1.5–1.75 times faster for integers, since its branches are then predictable. slice::sort_unstable, which shares several of these ideas, is 1.1–1.2 times faster on random integers from 100 elements on (it merges short parts through a buffer, which is only sound for types without interior mutability), but this sort is 1.9 times faster on 20 integers, 1.03–1.14 times faster on random strings and as fast or faster with 256-byte elements

Heap

Heap sort is an unstable, in-place, O(n log n) sorting algorithm with constant stack. It arranges the slice into a max-heap, a tree stored in the slice itself in which no element is smaller than its children, so the largest element is at the root; it then repeatedly moves the root to the end of the heap, shrinks the heap by one and restores the heap order. Building the heap takes O(n) comparisons and each of the n removals O(log n), whatever the input. This implementation uses five optimizations:

• Sorted and reverse-sorted input is recognised: the slice is first scanned for one ascending or strictly descending run; if it covers the whole slice, the slice is left alone or reversed, at n−1 comparisons (usually two or three on other input). Heap sort itself would spend n·log₂ n comparisons on sorted input.
• Bottom-up removal: the textbook sift-down compares the element moved to the root with the larger child at every level, but that element comes from the end of the heap and usually sinks almost to the bottom anyway. Instead, the vacant root moves down to a leaf along the larger children, one comparison per level, and the element moves up from there, usually by a level or two (Wegener's bottom-up heap sort): about n·log₂ n comparisons instead of 1.7–1.85·n·log₂ n.
• Holes instead of swaps: the element being placed is held outside the slice, and each level moves one element into the vacant slot instead of swapping two, one move instead of three.
• Four children per node for large heaps and small elements: a heap with four children per node has half as many levels, at three comparisons per level instead of one (about 1.5·n·log₂ n in all). That pays from 64 KiB of elements on, where every level of the heap costs a cache miss: on random input 1.15–1.35 times faster for integers from 100,000 elements on, 1.1–1.4 times for strings and 1.25–2 times for 64-byte elements; on nearly sorted strings 1.05–1.15 times slower. It also pays for elements of at most 8 bytes at any length, whose comparisons are so cheap that a level costs about the time to load the children, compare them and find the next ones: 1.15–1.25 times faster for integers in cache (&str, as small as a u128 but slower to compare, would be 1.05–1.15 times slower, so 16-byte elements keep two children below 64 KiB).
• Short chains from one level to the next: each level of a removal waits for the comparison before it, which says where the next children are. Every child is loaded straight from the first child's index, and for elements of up to 16 bytes the larger child and its own first child are chosen by selects between values computed beforehand; with four children the winners of the first round are selected as pointers, so the values already loaded are compared instead of being loaded again. This alone makes integers sort 1.25–1.3 times faster on four children per node. Larger elements, which compare by chains of branches that would turn the selects back into branches, keep arithmetic.

Together, against the textbook heap sort, this is 1.1–1.25 times faster for integers up to 1000 elements and 1.4–1.85 times from 10,000 on, 1.05–1.4 times for strings from 1000 elements on and 1.3–2.2 times for 256-byte elements. Only sawtooth input of 1000–2000 integers, whose short periods make three comparisons per level cost more than the levels saved, would sort 1.02–1.05 times faster on two children per node.

Examples

Rust usage with integers:

use a::sort::heap;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
  heap(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

Rust usage with strings:

use a::sort::heap;

fn main() {
  let mut words = vec!["pear", "apple", "fig"];
  heap(&mut words);
  assert_eq!(words, vec!["apple", "fig", "pear"]);
}

Efficiency

• Time complexity:
  • Worst: O(n log n)
  • Average: O(n log n)
  • Best: O(n), when the input is sorted or reverse sorted
• Comparisons:
  • Best (sorted, reverse sorted): n−1
  • Random input: about n·log₂ n + 0.6n (≈ 10,500 for n = 1000, against ≈ 16,800 for the textbook heap sort); about 1.5·n·log₂ n with four children per node, from 64 KiB of elements on and for elements of at most 8 bytes (≈ 14,600 for n = 1000)
  • Worst: O(n log n), on every input
• Moves: about n·log₂ n, and about 0.5·n·log₂ n with four children per node
• Space complexity: O(1) stack, no allocation (in-place)
• Stability: unstable (equal elements may be reordered)
• Adaptivity: not adaptive, except to sorted and reverse-sorted input. Heap sort jumps around the slice, so slice::sort_unstable and this crate's Quick sort, which falls back to heap sort only when its pivots keep failing, are faster: 2–3.4 times for random integers from 64 elements on, 1.6–6 times for strings and 1.1–3.5 times for 256-byte elements. Heap sort's strength is its guarantee: O(n log n) on every input, in place, with constant stack

Tim

Tim sort is a stable, O(n log n) merge sort that makes use of the order already in the input; Tim Peters designed it for Python's list.sort in 2002. It splits the slice into runs, the longest stretches that are ascending or strictly descending, and reverses the descending ones. Runs shorter than a minimum length (16 to 32 elements, chosen so that the slice splits into a power of two runs or slightly fewer) are extended to it by insertion sort (to twice it for elements of at most 8 bytes), and runs are merged as they are found, in an order kept on a stack, until one is left. Random input has short runs and costs as much as any merge sort, but input made of a few long runs costs little more than finding them. This implementation uses a buffer of n elements, kept on the stack when it fits in 4 KiB and otherwise allocated when the first merge needs it, and six optimizations:

• Galloping: before a merge, two searches find the elements of the left run that are not greater than the first of the right run, and those of the right run that are not smaller than the last of the left run; they are already in place and stay out of the merge. During a merge, once one run has supplied seven elements in a row, the merge gallops: it finds how many more of that run's elements come next by probing 1, 2, 4, … elements ahead and binary searching the last gap, and moves them as a block, k elements for about 2·log₂ k comparisons. The threshold drops while galloping pays off and rises when it does not, so random input hardly ever gallops.
• Powersort merge policy: two runs are merged once the boundary between them lies deeper in a perfectly balanced merge tree over the slice than the boundary after them (Munro and Wild's powersort, used by CPython's Tim sort since Python 3.11). This merges in close to the cheapest order possible and never keeps more than 65 runs on the stack; Peters' original stack rules are 1.04–1.12 times slower on input made of runs of varying lengths and no faster elsewhere.
• Bidirectional, branchless merging: like Merge sort, a merge copies both runs out and merges them back from both ends at once, two independent chains of comparisons that copy from an address chosen by the comparison instead of branching on it; each end counts its own winning streaks and gallops on its own. Tim sort's classic merge, which copies only the shorter run out and merges from one end, is 1.15–1.45 times slower on random input, but moves less when one run is much longer than the other, so merges of runs more than four times as long as each other still use it (1.05–1.55 times faster on sorted input with elements appended).
• Pair insertion: short runs are extended by inserting elements two at a time, scanning from the right; the larger one is carried left first and the smaller one goes on from where it stopped, so the elements both pass move once. Peters' binary insertion makes fewer comparisons, but each probe waits for the previous one and its moves go through memmove: it is 1.2–1.9 times slower on random input, strings included. Runs of 16 to 32 elements (CPython uses 32 to 64) are 1.1–1.2 times faster on 100 to 1000 random elements when every short run is extended by insertion.
• Branchless short runs for small elements: each insertion ends in a mispredicted branch, which for elements of at most 8 bytes costs more than everything else, so for them a natural run shorter than the minimum length is extended to twice it (32 to 64 elements, as in CPython; natural runs of the minimum length are kept), and a short run that starts with fewer than four sorted elements, or whose next elements dip below its end, is sorted by Merge sort's branchless sort for short slices, which notes the descents and leaves alone what is in order. Against insertion this is 1.1–1.3 times faster for integers on random input and 1.1–1.2 times with few distinct keys, and up to 1.25 times slower on short slices that are nearly sorted in small steps; the runs of twice the length are another 1.08–1.3 times faster on random input and with few distinct keys and 1.05–1.45 times on input made of runs up to 1000 elements, up to 1.07 times slower on runs of about 45 elements and 1.05–1.75 times on a sawtooth of 40 to 1000 elements.
• No allocation for small slices or single runs: the buffer lives on the stack while it fits in 4 KiB (512 u64s, say), and is otherwise allocated when the first merge needs it, so sorted and strictly descending input never allocates.

Examples

Rust usage with integers:

use a::sort::tim;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
  tim(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

A sorted log with late entries appended is two runs, merged mostly by galloping:

use a::sort::tim;

fn main() {
  let mut times: Vec<u32> = (0..1000).map(|i| i * 10).collect();
  times.extend([15, 4005, 9999]);
  tim(&mut times);
  assert!(times.windows(2).all(|w| w[0] <= w[1]));
}

Equal keys keep their original order (cards are compared by rank only):

use a::sort::tim;
use std::cmp::Ordering;

#[derive(Debug, PartialEq, Eq)]
struct Card(u8, char);

impl Ord for Card {
  fn cmp(&self, other: &Self) -> Ordering {
    self.0.cmp(&other.0)
  }
}

impl PartialOrd for Card {
  fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    Some(self.cmp(other))
  }
}

fn main() {
  let ranks = [3, 1, 3, 0, 1, 3, 0, 2, 1, 0];
  let mut cards: Vec<Card> = "abcdefghij".chars().zip(ranks).map(|(c, r)| Card(r, c)).collect();
  tim(&mut cards);
  let order: String = cards.iter().map(|c| c.1).collect();
  assert_eq!(order, "dgjbeihacf");
}

Efficiency

• Time complexity:
  • Worst: O(n log n)
  • Average: O(n log n)
  • Best: O(n), when the input is sorted or strictly descending; O(n + n·H) for input made of runs, H ≤ log₂ r being the entropy of the lengths of its r runs
• Comparisons:
  • Best (sorted, strictly descending): n−1, with no moves (strictly descending input is reversed)
  • Nearly sorted: about 1,180 comparisons for n = 1000 with 10 random elements appended and 1,800 with 10 random pairs swapped (2,060 for elements of at most 8 bytes; merge sort: about 1,800 and 3,900)
  • Random input: about 1.06·n·log₂ n for elements of at most 8 bytes (≈ 10,580 for n = 1000, against ≈ 10,290 for merge sort) and about (1.05–1.17)·n·log₂ n for larger ones (≈ 11,700, merge sort ≈ 9,570), whose short runs are built by linear insertion: more comparisons than a binary search would make, but less time
  • Worst: O(n log n)
• Space complexity: O(n) extra (one buffer of n elements, on the stack up to 4 KiB, otherwise allocated once, and only if a merge is needed) plus a stack of at most 65 runs
• Stability: stable (equal elements keep their relative order)
• Adaptivity: very good. Against this crate's merge sort, which no longer copies a level out before merging it and splits long merges, and so is the faster of the two on input without long runs: 1.1–1.5 times slower on random input from 1000 elements on and up to 1.35 times on short runs of random content, but 1.2–1.5 times faster on nearly sorted integers and strings, 1.45–2.2 times on sorted input with elements appended and 1.7–11 times on reverse-sorted input from 1000 elements on. Against slice::sort, which also finds runs: 1.2–1.45 times slower on random integers from 1000 elements on and 1.35–1.45 times on random strings (1.5 times faster on a million), but 1.5–3.7 times faster on nearly sorted input, 1.9–3.4 times on appended elements and 1.6–3.6 times on input made of runs of √n elements from 10,000 on, for integers and strings

Intro

Intro sort (introspective sort) is an unstable, in-place, O(n log n) sorting algorithm designed by David Musser in 1997: a quick sort that watches its own progress. Quick sort partitions the slice around a pivot and sorts the two parts the same way; with good pivots each level halves the parts, but no cheap pivot rule is good on every input, and bad pivots make it quadratic. Intro sort counts the levels, and a part still being partitioned after 2·⌊log₂ n⌋ levels is handed to Heap sort, which is O(n log n) on every input; typical input never reaches the limit and keeps quick sort's speed. Short parts are left to insertion sort. This implementation keeps Hoare's partitioning comparisons and uses five optimizations:

• Sorted and reverse-sorted input is recognised: the slice is first scanned for one ascending or strictly descending run; if it covers the whole slice, the slice is left alone or reversed, at n−1 comparisons (usually two or three on other input).
• Branchless block partitioning: Hoare's scheme scans from both ends for elements on the wrong side of the pivot and swaps them, and each scan stops at an unpredictable element, a mispredicted branch. Here each end compares a block of 128 elements first (Edelkamp and Weiss's choice; 1.02–1.06 times faster than 64 on random input from 1000 elements on), recording the misplaced ones by offset without branching, and then exchanges as many misplaced pairs as both blocks have (Edelkamp and Weiss's BlockQuicksort), in a cycle of two moves per pair instead of a swap's three. Same comparisons as Hoare's scheme; on random input 1.8–2.7 times faster for integers, 1.7–2.2 times for strings and 1.4–2.1 times for 64-byte elements. The block scans are unrolled by 8, another 1.03–1.08 times on random input and 1.1–1.25 times on nearly sorted input, where the scans are nearly all the work.
• Equal keys split evenly: as in Hoare's and Musser's scheme, an element equal to the pivot stops the scans on both sides, so equal keys are spread over both parts, and input with few distinct keys, even all equal but one, costs O(n log n) without ever reaching the depth limit.
• Pivots away from the ends, from a ninther on long parts: the median of the elements at a quarter, half and three quarters of the part, and from 128 elements on the median of three medians of three (Tukey's ninther), 1.04–1.13 times faster on sawtooth input of 100,000 elements or more. Musser samples the first, middle and last elements; swapping the pivot to the front then moves the smallest element of a sorted stretch into the middle, where the next sample finds it again, so sorted input with a few elements appended keeps getting the second smallest element as its pivot until the depth limit gives up: quartiles are 1.2–4 times faster there.
• Insertion sort while the part is fresh: parts of at most 24 elements (Musser: 16) are insertion sorted as soon as partitioning leaves them, still in the cache, instead of in one pass over the whole slice at the end, which reads the whole slice once more and is 1.05–1.15 times slower for strings.

Examples

Rust usage with integers:

use a::sort::intro;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
  intro(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

Rust usage with strings:

use a::sort::intro;

fn main() {
  let mut words = vec!["pear", "apple", "fig"];
  intro(&mut words);
  assert_eq!(words, vec!["apple", "fig", "pear"]);
}

Efficiency

• Time complexity:
  • Worst: O(n log n), guaranteed by the heap sort fallback
  • Average: O(n log n)
  • Best: O(n), when the input is sorted or reverse sorted
• Comparisons:
  • Best (sorted, reverse sorted, all equal): n−1
  • Random input: about (1.1–1.19)·n·log₂ n (≈ 11,800 for n = 1000); insertion into parts of up to 24 elements costs more comparisons than partitioning them further would, but less time
  • Few distinct keys: about 0.85·n·log₂ n; unlike Quick sort, intro sort does not take all copies of a pivot out at once
  • Adversarial input: McIlroy's adversary, which answers comparisons so as to make every pivot bad, drives partitioning alone to 9.1 million comparisons for n = 10,000; with the heap sort fallback the whole sort makes about 470,000
• Space complexity: O(log n) stack, no allocation (in-place)
• Stability: unstable (equal elements may be reordered)
• Adaptivity: adaptive to sorted and reverse-sorted input, and cheap on nearly sorted input, where Hoare's scheme moves only what is misplaced. Against Quick sort: 1.35–1.55 times slower on random integers from 1000 elements on, 1.06–1.13 times on random strings and 1.5–3.8 times with few distinct keys, but 1.2–1.65 times faster on random 64-byte elements and 1.3–3.6 times faster on nearly sorted input. Against slice::sort_unstable: 1.45–1.75 times slower on random integers and within 1.07 times on random strings, but 1.08–1.55 times faster on random 64-byte elements and 1.5–3.7 times on nearly sorted input. Against Heap sort, which it falls back to: 1.3–2.4 times faster on random integers, 2.1–6.7 times on strings and 1.5–4.4 times on 64-byte elements

Shell

Shell sort, published by Donald Shell in 1959, is an unstable, in-place insertion sort with a gap. A pass with gap h insertion sorts every chain of elements h apart, so an element far from its place travels there in steps of h instead of one slot at a time; the passes use a decreasing sequence of gaps ending with 1, a plain insertion sort that the earlier passes leave with little to do. How fast it is depends almost entirely on the gaps. This implementation uses five optimizations:

• Sorted and reverse-sorted input is recognised: the slice is first scanned for one ascending or strictly descending run; if it covers the whole slice, the slice is left alone or reversed, at n−1 comparisons (usually two or three on other input).
• Hole shifting: an element is read out once, the greater elements before it on its chain shift one place along the chain each, and it is written once into the slot left free, one move per step instead of a swap's three.
• The gaps that are fastest, not the fewest comparisons: Ciura's sequence (1, 4, 10, 23, 57, 132, 301, 701, then times 2.25) makes 1.1–1.27 times fewer comparisons than Sedgewick's 1982 one (1, 8, 23, 77, 281, 1073, …), but nearly every insertion ends in a mispredicted branch, and Sedgewick's gaps grow by a factor of about 4, so they take fewer passes: for elements larger than 8 bytes they are 1.05–1.35 times faster, strings included (except random strings from a million elements on, 1.1 times slower). Elements of at most 8 bytes use Ciura's gaps, which suit the window below.
• A branchless window for small elements: in a pass over a slice far from sorted, how far an element moves along its chain is about as hard to predict as a coin toss (with Ciura's gaps 0 steps 44% of the time, 1 step 26%, 2 steps 14%, 3 steps 8%, 4 or more 8%). For elements of at most 8 bytes, each element is compared with the 4 elements before it on its chain at once, how many it passes is computed as a number, and the 4 slots it can move into are rewritten from copies held in registers, each chosen by two selects on that number; only the 8% that pass all 4 go on with a branch per step. On random input this is 1.65–1.9 times faster for integers.
• The window only where it pays, judged by the insertions themselves: where the slice is nearly sorted or its order follows a pattern, insertion's branches are predictable and the window's extra comparisons and writes are wasted (a pass can be up to 5 times slower with it), and how many elements move does not tell the two apart, but how regularly they move does. So a pass is made in blocks of 512 elements, and each block counts, at no measurable cost, how predictable its insertions were and chooses the window for the next block only if they were not: inserted plainly, the runs of consecutive elements that moved and the steps they took beyond the first (2·runs + 0.35·steps > 0.42 per element); through the window, how often the number of elements passed differs from the one before (more than 0.42 per element). As branch predictors also learn short patterns, the last 32 elements of each block note their steps too, and a block whose steps repeat with a period of at most 16 is followed by plain insertion. Against taking the window whenever the pass before moved more than a quarter of the elements: 1.2–1.85 times faster on sawtooth input of 1000 to a million integers with periods from 4 to n/8 (but a period of √n from 100,000 elements on, as fast to 1.1 times slower), 2.1–2.45 times on organ-pipe input, 1.05–1.15 times on nearly sorted input, 1.05–1.25 times with 4 distinct keys, and as fast on random input (sorted runs of about √n random elements are 1.03–1.25 times slower below 10,000 elements).

Examples

Rust usage with integers:

use a::sort::shell;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
  shell(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

Rust usage with strings:

use a::sort::shell;

fn main() {
  let mut words = vec!["pear", "apple", "fig"];
  shell(&mut words);
  assert_eq!(words, vec!["apple", "fig", "pear"]);
}

Efficiency

• Time complexity:
  • Worst: O(n^(4/3)) with Sedgewick's gaps; no bound is known for Ciura's, which were found by experiment
  • Average: no exact bound is known; measured, 1.6–2.8·n·log₂ n comparisons up to a million elements (no gap sequence is known to make Shell sort O(n log n))
  • Best: O(n), when the input is sorted or reverse sorted
• Comparisons:
  • Best (sorted, reverse sorted, all equal): n−1
  • Random input: about (1.6–2)·n·log₂ n with Sedgewick's gaps (≈ 15,900 for n = 1000) and (2.1–2.8)·n·log₂ n with Ciura's gaps and the window (≈ 21,300), whose unnecessary comparisons are cheap for small elements
• Space complexity: O(1) extra (in-place)
• Stability: unstable (an insertion along a chain can carry an element past an equal one between the two)
• Adaptivity: the passes do less on nearly sorted input. Against classic Shell sort with Ciura's gaps: 1.65–1.9 times faster on random integers from 1000 elements on, up to 1.75 times on nearly sorted ones, 1.3–1.4 times with few distinct keys and 1.1–1.2 times on organ-pipe input; on sawtooth input of 1000–100,000 integers with periods from 4 to n/8 from 1.15 times slower (a period of 16 at 1000 elements) to 1.35 times faster, mostly within 1.1 times either way; 1.05–1.4 times faster on strings and 1.03–1.3 times on 64-byte elements. Against Comb sort: 3.55–4 times slower on random integers from 1000 elements on and 1.8–2.65 times on nearly sorted ones or with few distinct keys (1.15 times faster on 100 nearly sorted ones), but 1.1–2.5 times faster on strings that have few distinct keys or follow a pattern, and 1.6 times on 1000 nearly sorted strings (as fast on longer ones). Against Heap sort: 1.45–1.8 times slower on random integers from 1000 elements on, 1.1–1.6 times on nearly sorted ones and 1.1–1.25 times with few distinct keys, about as fast on random strings, and faster on strings that are nearly sorted or patterned

Drift

Drift sort is a stable, O(n log n) sorting algorithm designed by Orson Peters and Lukas Bergdoll in 2024; it has been the stable sort of Rust's standard library since 1.81. It drifts between merge sort and quick sort: it scans for natural runs, ascending or strictly descending, but keeps only those of at least about √n elements (min(n/2, 32) below 4096 elements), and leaves everything else as unsorted chunks. Runs and chunks are combined in powersort's merge order: two adjacent unsorted chunks are simply taken together, while an unsorted chunk that meets a sorted run is first sorted by a stable quick sort and then merged. Random input ends up as one chunk for quick sort, which handles repeated keys in O(n log k); input made of long runs is merged like Tim sort's. This implementation uses a buffer of n elements, kept on the stack when it fits in 4 KiB and otherwise allocated when first needed, and nine optimizations (ratios measured with new input for every sort):

• This crate's best parts: runs are merged by Tim sort's merge (skipping elements already in place, merging from both ends at once without branching, galloping through runs that interleave in blocks, and running two merges at once once galloping has not paid off: 1.25–1.5 times faster on runs of random content); short parts are sorted by Merge sort's branchless short-run sort; and a quick sort still partitioning after 2·log₂ n levels hands the part to merge sort, so the sort is O(n log n) on any input.
• Pivot samples at several scales: Quick sort's ninther and evenly spaced pseudo-median sample at one scale, which periodic input whose period divides the spacing defeats (a sawtooth of 1000 elements cost 2.4 times the standard library's time). The samples lie in three sections of an eighth of the width, centred at the middle and 3/8 of the width to either side, recursively: 9 samples at two scales from 64 elements, 27 at three from 1024, three times as many for every 16 times the length. The sawtooth then costs 3.3–3.7 times less and random input 1–2% fewer comparisons.
• Branchless stable partitioning: each element is compared with the pivot and copied into the buffer, to the front if it goes left and to the back otherwise, from an address the comparison selects, and both parts are copied back, the back one reversed; a partition that moved nothing skips the copies back (1.05–1.3 times faster for integers with 2 distinct keys). Elements larger than 8 bytes are compacted in place as they go left, only the right part passing through the buffer, with the pivot moved into a local as its only live copy and a guard that restores every element if a comparison panics: 1.2–1.3 times faster on random 64-byte elements, 1.2–1.5 times with repeated keys, 1.1–1.2 times on random strings from 10,000 elements.
• Repeated keys in one pass, without copying the pivot: when a part's pivot is no greater than the pivot of the partition that produced the part, every element equal to it is taken out in one pass; the earlier pivot is found in place (the standard library compares a bitwise copy, sound only for types without interior mutability). Where no earlier pivot bounds a part, it is first scanned for an element smaller than the pivot, a comparison or two on most input, which spares a partition that moves nothing: 1.08–1.25 times faster for integers with 2 distinct keys.
• No per-element bookkeeping: the partition loop is split at the pivot and at the earlier pivot instead of checking for them at every element, and for elements of at most 8 bytes it is unrolled by 4.
• Short parts noted for order and merged in place: a part of up to 32 elements of at most 8 bytes is scanned for descents with one comparison per element and no branch on the answers; runs and stretches of the merge tree without one are left alone, the rest is sorted by the short-run sort, and every merge reads its halves where the level below left them and writes the other place, so no level is copied out before it is merged. The merges leave no stale copy behind when a comparison mutates its arguments: a merge of up to 16 elements decides the order before it copies anything, a longer one copies the few elements compared after their copy was written once more (1.03–1.05 times slower on random integers of 100 to 10,000 elements than merges that compare stale copies, which are sound only for types without interior mutability).
• Short slices adapt too: a slice of up to 64 elements of at most 8 bytes gets the same scan for descents: none and it is left alone, one at every element and it is reversed, at most one per 8 elements and the rest is inserted into the sorted prefix, otherwise it is sorted with the descents found (1.2–3 times faster than scanning for a prefix run and sorting the rest on random, few-keys, sorted, reverse-sorted or appended input of 8–64 integers; 1.1–1.25 times slower on 8–28 nearly sorted ones). Larger elements are scanned for a sorted or strictly descending prefix and the rest inserted, without a buffer, up to 28 elements (40 beyond 32 bytes), and up to twice the small sort's length sort each chunk as soon as it is found and merge the chunks, with no chunk scanned twice.
• Runs cut by a chunk boundary are taken back: a natural run whose rest falls short of the length a run must have is probed with one or two comparisons and, if they are in order, scanned backwards into the unsorted chunk before it, the boundary moving with it: 1.05–1.2 times faster on input made of runs of about √n elements.
• No allocation for small slices or single runs: the buffer lives on the stack while it fits in 4 KiB and is otherwise allocated when first needed; short slices of large elements are insertion sorted and need none.

Examples

Rust usage with integers:

use a::sort::drift;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
  drift(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

Equal keys keep their original order (cards are compared by rank only):

use a::sort::drift;
use std::cmp::Ordering;

#[derive(Debug, PartialEq, Eq)]
struct Card(u8, char);

impl Ord for Card {
  fn cmp(&self, other: &Self) -> Ordering {
    self.0.cmp(&other.0)
  }
}

impl PartialOrd for Card {
  fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    Some(self.cmp(other))
  }
}

fn main() {
  let ranks = [3, 1, 3, 0, 1, 3, 0, 2, 1, 0];
  let mut cards: Vec<Card> = "abcdefghij".chars().zip(ranks).map(|(c, r)| Card(r, c)).collect();
  drift(&mut cards);
  let order: String = cards.iter().map(|c| c.1).collect();
  assert_eq!(order, "dgjbeihacf");
}

Efficiency

• Time complexity:
  • Worst: O(n log n), guaranteed by the merge sort fallback of the quick sort
  • Average: O(n log n), and O(n log k) with k distinct keys
  • Best: O(n), when the input is sorted or strictly descending
• Comparisons:
  • Best (sorted, strictly descending): n−1, with no moves (strictly descending input is reversed)
  • Random input: about (1.06–1.12)·n·log₂ n (≈ 11,200 for n = 1000, the standard library 10,600; elements of at most 8 bytes trade about 4% more comparisons for fewer mispredicted branches)
  • Few distinct keys: about 0.22–0.28·n·log₂ n with 2 keys and 0.38–0.57·n·log₂ n with 16 (≈ 2,800 and 5,700 for n = 1000, against 7,050 and 9,390 for Tim sort with elements of at most 8 bytes and 5,290 and 10,380 with larger ones); about 2,050 with 10 random pairs swapped and 7,100 on a sawtooth of 1000
• Space complexity: O(n) extra (one buffer of n elements, on the stack up to 4 KiB, otherwise allocated once and only when needed; the standard library makes do with about n/2 for large inputs) plus O(log n) stack
• Stability: stable (equal elements keep their relative order)
• Soundness: a comparison that panics, answers inconsistently or mutates its arguments through interior mutability never leaves a stale copy, a duplicate or a hole behind
• Adaptivity: adaptive to runs of √n elements or more, even where a chunk boundary cuts them, and to repeated keys. Against slice::sort, the standard library's drift sort, with new input for every sort: 1.3–3 times faster on 8–64 random integers, 1.03–1.06 times slower on 100–100,000 and as fast beyond; 1.05–1.07 times slower on random strings up to 1000 elements, 1.03–1.1 times faster from 10,000 and 1.7 times on a million; 1.1 times slower on random 64-byte elements up to 100 and 1.03–1.25 times faster from 1000; 1.05–1.9 times faster with few or √n distinct keys from 1000 elements and 1.25–1.65 times on a sawtooth of 1000; and 1.4–8 times faster on nearly sorted, appended, block-wise sorted input or runs of √n elements (runs from 10,000 elements on). Against Tim sort: 1.05–1.3 times faster on random integers from 1000 elements on, 1.4–1.65 times on random strings and 1.2–1.3 times on 64-byte elements, 1.6–9.3 times with few distinct keys (3.4–9.3 times for integers) and 1.25–2.55 times on sawtooth input up to 100,000 elements; 1.1–1.4 times slower on nearly sorted integers (1.15–2 times for strings) and 1.05–1.4 times slower on runs of √n elements, which Tim sort keeps whole

Counting

Counting sort, described by Harold Seward in 1954, is the first sort of this library that does not compare elements with each other. It finds the smallest and the largest key, counts how many times each of the k keys in between occurs, and turns the counts into the sorted order, in O(n + k) time whatever the order of the input: faster than any comparison sort when k is not much larger than n, as with bytes, small integers or values in a known range. Keys are primitive integers, chars and bools (the sealed IntegerKey trait). It comes in two forms:

• counting sorts the keys themselves. Equal keys cannot be told apart, so the slice is simply rewritten from the counts: so many copies of the smallest key, then so many of the next.
• counting_by_key sorts any type by such a key, stably: the counts become 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, which is then copied back. This is counting sort as radix sort uses it. key is called exactly once per element.

A range of keys too large to count panics, leaving the slice as it was: one of more than 65,536 keys and more than four per element. Any range of a one- or two-byte type is allowed. This implementation uses six optimizations:

• Sorted and reverse-sorted input is recognised: counting scans for one ascending or one non-increasing run, 16 neighbours at a time with no exit inside a block, which the compiler vectorizes, and counting_by_key checks for one ascending or one strictly descending run in the pass that reads the keys; a slice that is one run is left alone or reversed, and nothing is counted.
• Eight count tables or segments for small ranges: incrementing a count waits for the increment before it to reach memory, so a few keys repeating make a chain of dependent increments. counting counts into eight tables, one element after the other into the next, with at most 2048 keys and 16 elements per key (3–5 times faster with a few distinct keys and on runs of bytes); counting_by_key cuts the slice into eight segments with their own places for every key, after those of the segments before them, with at most 256 keys and 16 elements per key, which keeps it stable (1.6–2.3 times faster with four distinct keys, 2.4–2.9 times on runs of bytes).
• Runs of equal keys do not wait on each other with one table or segment either: counts do not depend on the order of the keys, so one table is counted walking four quarters of the slice side by side (for counting, with u16 counts, or when the first values are mostly in order), and counting_by_key places four keys at a time, all four places read before any is written back: 2.2–2.6 times faster on nearly sorted input with sixteen elements per key, 1.4–1.7 times on nearly sorted counting_by_key input, and counting 1.05–1.3 times faster on random u8 and u32 values.
• Keys written ahead of their counts: counting writes each key 4 times (8 for one- and two-byte types, in one store) whatever its count, and only a count above that takes a branch; branching on every count mispredicts when there are about as many keys as elements and counts of 0, 1 and 2 are all common (2.5–5 times faster there). A range with 32 or more keys per element skips blocks of 8 empty counts at once instead.
• Keys read once: counting_by_key keeps the keys in a buffer as it reads them, and counts and places from it (1.05–1.25 times faster than calling key again on random keys); the counts and places can then be trusted without checking, and if key panics, no element has moved yet.
• No allocation for small sorts: counts (u16 up to 65,535 elements, u32 up to u32::MAX), keys and the element buffer each live on the stack up to 4 KiB; the places of counting_by_key are summed four at a time, one addition per four waiting for the one before it (1.1–1.25 times faster on random keys over four times as many keys as elements).

Examples

Rust usage with integers:

use a::sort::counting;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
  counting(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

Sorting by a key, stably (equal lengths keep their order):

use a::sort::counting_by_key;

fn main() {
  let mut words = vec!["pear", "fig", "banana", "kiwi", "apple", "lime"];
  counting_by_key(&mut words, |w| w.len());
  assert_eq!(words, vec!["fig", "pear", "kiwi", "lime", "apple", "banana"]);
}

Efficiency

• Time complexity:
  • Worst, average and best: O(n + k) for k possible keys between the smallest and the largest
  • Sorted and reverse-sorted input (strictly descending for counting_by_key): O(n), one scan
• Comparisons: none between elements, except the scan for a sorted or reverse-sorted run, which leaves random input after a block or two
• Calls to key (counting_by_key): exactly n
• Space complexity: O(k) counts for counting; O(n + k) for counting_by_key (a buffer of n elements, one of n keys and the places); each on the stack up to 4 KiB, otherwise allocated once
• Stability: counting_by_key is stable; counting cannot tell equal keys apart
• Against the textbook counting sort: counting is 3–5.5 times faster on random integers with about as many distinct keys as elements, 1.7–3.1 times with four distinct keys and 9–80 times on sorted, reverse-sorted and all-equal input; counting_by_key is 1.05–1.6 times faster on random keys, 1.35–2.2 times with four distinct keys and 6–20 times on sorted and all-equal input, but 1.02–1.15 times slower on reverse-sorted input with repeated keys, random bytes from 10,000 elements on and 1000–10,000 random keys with sixteen times fewer keys than elements, where keeping the keys costs more than it saves (nearly sorted input, which was 1.02–1.15 times slower, now takes 0.6–0.85 times as long as it did)
• Against the standard library, from 100 elements on: counting is 3.2–10 times faster than slice::sort_unstable on random u32 and u64 with about as many distinct keys as elements, 1.9–4 times with four times as many, 2.8–4 times with four distinct keys, 2.2–12 times on nearly sorted input and 9–15 times on random bytes from 1000 elements on; counting_by_key is 2.9–7 times faster than slice::sort_by_key on random u32 keys with about as many distinct keys as elements and 1.6–2.3 times with four distinct keys, and as fast on sorted input. On 16 elements both are up to 2 times slower on sorted or nearly sorted input, where the standard library's insertion sort shines

Radix

LSD radix sort, used on punched-card sorters since the 1920s, does not compare elements either. It reads every key as a number of a few digits and sorts the slice by each digit in turn, from the least significant to the most, with a stable counting pass; as each pass keeps the order the earlier ones made among equal digits, the slice ends up sorted by the whole key. For w-bit keys and r-bit digits that is ⌈w / r⌉ passes of O(n + 2^r) each, whatever the order of the input: unlike Counting sort, any range of keys can be sorted. Keys are the same as counting sort's (the sealed IntegerKey trait), signed integers read with their sign bit flipped. It comes in two forms: radix sorts the keys themselves, and radix_by_key sorts any type by such a key, stably, calling key exactly once per element. This implementation uses eight optimizations:

• Sorted and reverse-sorted input is recognised: radix scans for one ascending or one non-increasing run, 16 neighbours at a time with no exit inside a block, and radix_by_key checks for one ascending or one strictly descending run in the pass that reads the keys; a slice that is one run is left alone or reversed, and nothing is counted.
• Only the bits in which keys differ are sorted, in digits sized by the slice: one pass ORs together every key's difference from the first, and the span from its lowest to its highest set bit is cut into the fewest digits of equal width of at most log₂ n bits (at least 8 from 64 elements on, at most 12), the digit size CLRS derives for radix sort. Against byte digits with shared bytes skipped: 1.1–1.25 times faster on random integers from 10,000 elements on and 1.75–3.4 times on integers below n.
• Short slices count their digits side by side: every pass costs the sum of its counts however few elements it moves, 256 of them for an 8-bit digit. Below 80 elements per 8-bit digit (640 for 64-bit keys), the counts of up to eight 8-bit digits are kept in rows of eight lanes, one per digit (4 KiB), and turned into places by one vectorized running sum per lane for all digits at once, the first half of the rows summed upwards and the second downwards: fewer passes than log₂ n-bit digits take, for about the cost of one sum. This pays when the s passes saved against 6-bit digits make n·s² at least 144; otherwise, from 24 elements on, 6-bit digits are taken, whose 64 counts are summed while the pass before waits on memory. In lanes, radix sorts signed values as their bits, flipping the sign bit once before and once after the passes rather than in every pass. 1.15–1.8 times faster on 16 to 256 random u64s (radix_by_key: 1.15–1.6 times for 16-byte elements, 1.35–1.5 times for 72-byte ones), 1.1–1.45 times on 32 to 256 random u32s.
• One digit is a counting sort: when a single digit holds every bit in which the keys differ, its pass is this crate's Counting sort, with its count tables (radix, 2.4–5.4 times faster with four distinct values) or its segments (radix_by_key, 1.3–1.8 times faster with four distinct keys).
• Every count in one pass, and no copy back: the counts of all digits are made in one pass, a digit all keys share is skipped, and the passes move the slice into the buffer and back alternately. The counts of a digit become places four at a time, one addition per four waiting for the one before it (1.15–1.2 times faster on 100 random keys).
• Runs of a digit do not wait on each other: the counts walk four quarters of the slice side by side, as they do not depend on the order of the keys (1.6 times faster on nearly sorted input, whose high digits neighbours share), and every pass places four keys at a time, all four counts read before any is written back (1.7–2.2 times faster with four distinct wide keys).
• Large elements are moved once: when radix_by_key's passes would move at least 96 bytes of every element and the slice takes at most 16 MiB, the keys are sorted with the indices of their elements, which are then gathered once (1.25 times faster for 32-byte elements, up to 1.6 times for 72-byte ones).
• No allocation for small sorts: keys, elements and counts (u16 up to 65,535 elements, u32 up to u32::MAX) each live on the stack up to 4 KiB.

Examples

Rust usage with integers:

use a::sort::radix;

fn main() {
  let mut v = vec![i64::MAX, -1, i64::MIN, 0, 1 << 40];
  radix(&mut v);
  assert_eq!(v, vec![i64::MIN, -1, 0, 1 << 40, i64::MAX]);
}

Sorting by a key, stably:

use a::sort::radix_by_key;

fn main() {
  let mut v = vec![(3, 'a'), (1, 'b'), (3, 'c'), (0, 'd'), (1, 'e')];
  radix_by_key(&mut v, |&(k, _)| k);
  assert_eq!(v, vec![(0, 'd'), (1, 'b'), (1, 'e'), (3, 'a'), (3, 'c')]);
}

Efficiency

• Time complexity:
  • Worst, average and best: O(n·b/r) for keys that differ in b bits and digits of r bits (r ≈ log₂ n, between 8 and 12 from 64 elements on; 6 or 8 for short slices)
  • Sorted and reverse-sorted input (strictly descending for radix_by_key): O(n), one scan
• Comparisons: none between elements, except the scan for a sorted or reverse-sorted run
• Calls to key (radix_by_key): exactly n
• Space complexity: O(n) buffers (radix: n values; radix_by_key: n keys, n elements and, when gathering, 2n keys with indices) plus the counts; each on the stack up to 4 KiB, otherwise allocated once
• Stability: radix_by_key is stable; radix cannot tell equal values apart
• Against the textbook LSD radix sort (a pass per byte through a buffer copied back each time): radix is 1.15–1.8 times faster on random integers from 1000 elements on (1.9–2.3 times at 100 elements and 2.7–3.4 times at 16 against one that allocates its buffer), 2.6–16 times on integers below n, 12–35 times with four distinct values and 58–190 times on sorted input; radix_by_key is as fast to 1.2 times faster on random u32 keys of 16-byte elements, 1.45–2.4 times for 72-byte elements and 6–14 times with four distinct keys
• Against the standard library, from 1000 elements on: radix is 1.8–5 times faster than slice::sort_unstable on random u32s, up to 2.3 times on random u64s, 3–7.5 times on integers below n and 1.1–5 times on nearly sorted input; radix_by_key is 1.7–6 times faster than slice::sort_by_key on random u32 keys (16- to 72-byte elements) and up to 2 times on random u64 keys. On 100 to 256 random u32s radix is 1.15–1.75 times faster too. Its weaknesses are short slices of wide keys, where every pass costs its counts however few elements it moves (100 random u64s sort 1.4 times slower than with slice::sort_unstable on fresh input, 2.3 times on the same input over and over; 16 to 32 elements 1.6 (u32) to 3.2 (u64) times slower; radix_by_key on 100 random u64 keys of 16-byte elements is 1.15 times slower than slice::sort_by_key, of 72-byte elements 1.4 times faster), and a few distinct values spread over wide keys, which take every pass while the standard library partitions them away (four distinct random u32s take 2–2.9 times as long, u64s 2.8–5 times). For keys in a range of about n values, Counting sort is 1.07–1.8 times faster

Bucket

Bucket sort, as CLRS describes it, sorts n reals spread uniformly over [0, 1) by cutting the range into n buckets of equal width, moving every element into the bucket its key falls in, sorting each bucket by insertion and reading the buckets out in order: O(n) expected time, as each bucket holds about one element. This implementation cuts the range from the smallest to the largest key of each level into one bucket per element, at most 4096 (65,536 for a level of fewer than 131,072 keys that spread over its range), moves the elements into their buckets with a stable counting pass, sorts runs of buckets of at most 16 elements by one insertion sort, and cuts larger buckets again over their own range. Floats are cut by value at the first level; integers, and floats below it, by their bits, which bounds the depth by the width of the key, so that skewed input, which makes the textbook version quadratic, costs at most a few more levels. Keys are primitive integers, chars, bools, f32s and f64s (the sealed BucketKey trait), floats sorted as f64::total_cmp orders them. It comes in two forms: bucket sorts the keys themselves, and bucket_by_key sorts any type by such a key, stably, calling key exactly once per element. This implementation uses twelve optimizations:

• Sorted and reverse-sorted input is recognised (non-increasing input too for bucket_by_key, whose runs of equal keys are reversed back), and left alone or reversed.
• Keys are read once, as bits that order as they do: signed integers and floats are rewritten in place as unsigned integers in one pass that also finds their range, and back at the end, so every comparison is one of integers.
• Floats crowded at zero are cut by their bits: values over many orders of magnitude crowd near zero when cut by value; when the three buckets there hold more than half the keys, the level is counted again by bits and moved by the cut with the smaller largest bucket (2.6–3 times faster on floats of random exponents).
• Runs of keys in one bucket do not wait on each other: keys are counted and placed four at a time, and a level with at least four keys per bucket counts into four interleaved tables, from 16 into eight (1.8–3 times faster on powers of two, 1.3–2 times with four distinct keys, 1.7 times on nearly sorted input).
• Keys that crowd a few buckets are counted and moved in groups (bucket): the tables split the chains of a count, but not those of the moves. A level of at least 512 keys, two or more per bucket, whose eight keys at even distances share buckets in at least four pairs is cut into groups of keys side by side, each counted into tables of its own and moved by places of its own: two groups, or four of two tables each from eight keys per bucket on (1.02–1.15 times faster on powers of two at 10,000 elements, 1.05–1.3 times at 100,000 and 1.3–1.45 times at 1,000,000; 1.12–1.35 times with 4 to 16 distinct keys from 100,000 elements on; 1.12–1.3 times on f32s of random exponents from 10,000 on).
• One bucket per key up to 65,536 for keys that spread: cut into 4096 buckets, a level of 5000 to 130,000 keys holds 1 to 32 per bucket, which the insertion sorts or a second level pay for. A level of more than 4096 and fewer than 131,072 keys takes one bucket per key when 32 of its keys at even distances fall in at least 30 different buckets of 4096, unless fewer than 65,536 keys start mostly in order (1.2–2.9 times faster on random and uniform keys and keys below n from 10,000 to 130,000 elements; few distinct keys and keys crowding a few buckets keep 4096 buckets).
• Buckets are found once: a level of at most 2048 keys keeps the bucket of each key as it counts it.
• A level of one bucket per key, when there are fewer keys in its range than buckets, is sorted as it is moved (1.5 times faster on keys below n).
• Insertion without a branch for keys that move: each chunk of 32 keys is sorted with a branch when few keys moved in the chunk before, and otherwise by writing the larger and the smaller of a key and its neighbour without one (1.2–1.8 times faster on uniform keys).
• Large elements move once: bucket_by_key sorts parts of 64 KiB and at most 8192 elements of at least 64 bytes by the indices of their elements, which then move along the cycles of that permutation (1.1–2 times faster), and elements over 16 bytes that keys often pass in a run of small buckets by their positions.
• Keys are read by a loop fit for the size of the elements: a vectorized one up to 16 bytes, and loops that leave at the first key out of order beyond.
• No allocation for small sorts: up to 16 elements are sorted by insertion at once, and buffers and counts (u16 up to 65,535 elements) of up to 4 KiB each live on the stack; the counts become the starts of the buckets four at a time (1.03–1.07 times faster at 100–1000 elements).

Examples

Rust usage with integers and floats:

use a::sort::bucket;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
  bucket(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);

  let mut v = vec![0.42, -1.5, 0.0, f64::INFINITY, -0.0, 0.17];
  bucket(&mut v);
  assert_eq!(v, vec![-1.5, -0.0, 0.0, 0.17, 0.42, f64::INFINITY]);
}

Sorting by a key, stably (equal temperatures keep their order):

use a::sort::bucket_by_key;

fn main() {
  let mut cities = vec![("Oslo", 4.5), ("Cairo", 31.0), ("Lima", 19.25), ("Kyiv", 4.5)];
  bucket_by_key(&mut cities, |&(_, t)| t);
  let names: Vec<&str> = cities.iter().map(|c| c.0).collect();
  assert_eq!(names, vec!["Oslo", "Kyiv", "Lima", "Cairo"]);
}

Efficiency

• Time complexity:
  • Average, for keys spread evenly over their range: O(n), one or two levels of buckets of a few keys
  • Worst: O(n·w) for keys of w bits: a level divides the range of its keys by its number of buckets, from 17 to 4096 (65,536 below 131,072 keys), so an element passes at most ⌈w / 4⌉ levels (one more for floats), and while its bucket holds more than 4096 keys, a level takes at least 12 bits off
  • Sorted and reverse-sorted input (also non-increasing for bucket_by_key): O(n), one scan
• Comparisons: none to place elements; those of the insertion sorts within buckets of a few keys, and of the scan for a sorted or reverse-sorted run
• Calls to key (bucket_by_key): exactly n
• Space complexity: O(n) buffers (bucket: n keys; bucket_by_key: n keys and n elements, or 2n indices for large elements) plus the counts of a level; each on the stack up to 4 KiB, otherwise allocated
• Stability: bucket_by_key is stable; bucket cannot tell equal keys apart
• Against the textbook bucket sort (n buckets as vectors, each sorted by insertion, concatenated): bucket is 6.8–11 times faster on random and uniform u64s, 4.9–8 times on uniform f64s, 3–4.4 times with four distinct keys and 55–180 times on sorted and reverse-sorted input; bucket_by_key is 4.5–8 times faster on uniform u64 keys of 16-byte elements. On skewed input the textbook version is quadratic: f64s of random exponents take it 170 times as long at 10,000 elements, powers of two 7–33 times at 1000
• Against the standard library, from 100 elements on: bucket is 1.3–3 times faster than slice::sort_unstable on random and uniform integers, 1.7–3.7 times on uniform floats (against sort_unstable_by(f64::total_cmp)), 2–5.9 times on keys below n and 1.25–4.8 times on nearly sorted input; bucket_by_key is 1.3–3.1 times faster than slice::sort_by_key on random u64 keys of 16-byte elements, 2.3–4.8 times of 72-byte elements and 1.5–3.4 times on random f64 keys. Its weakness is keys that equal-width buckets do not spread, where the standard library gains from few distinct values: powers of two take 1.2–4.3 times as long up to 100,000 elements (about as long at 1,000,000), four distinct keys up to 1.5 times from 1000 to 10,000 elements (f64s 1.8–2.2 times from 1000 on), and f32s of random exponents (mostly zeros and infinities) up to 1.8 times; 16 elements take about as long. For 32-bit integers on large slices, Radix sort, which does not depend on how the keys are spread, is faster (1.4–1.6 times on random u32s from 100,000 elements on), but on random u64s it is 1.2–1.35 times slower

Pigeonhole

Pigeonhole sort gives every possible key from the smallest to the largest a hole of its own, puts each element into the hole of its key, and reads the holes out in order: O(n + k) time for k keys. This implementation keeps the holes in the slice itself: the keys are counted, which gives every hole its place, and each element out of place is then moved straight into the next free place of its hole, the element there taken out in turn, around the cycle until an element lands where the first one was. Every element moves at most once, in place, with no buffer for the elements; it is not stable. Keys are the same as counting sort's (the sealed IntegerKey trait), and so is the range rule. It comes in two forms: pigeonhole sorts the keys themselves, for which Counting sort, which rewrites equal values from their counts, is 2.2–7 times faster on random values and 1.4–2.25 times on nearly sorted ones, and pigeonhole_by_key sorts any type in place by such a key, calling key exactly once per element. This implementation uses eight optimizations:

• Sorted and reverse-sorted input is recognised (non-increasing input too, as the sort is not stable), and left alone or reversed.
• Large slices are placed by swaps: following a cycle, each step waits for the one before it, and for memory once the slice no longer fits the caches. From 32,768 elements on (more for large elements), unless the input is mostly in order, the element at every free place is swapped with the next free place of its own hole instead; the target of a swap depends on its own key only, so the processor overlaps the swaps' waits for memory (1.1–4.3 times faster from 100,000 elements on). Two holes count as one more element towards that length, the counts become the starts of the holes in place, and the holes with free places are listed without a branch (1.35–1.65 times faster from 40,000 elements on, 1.2–1.4 times from 20,000 with four keys per element).
• A few distinct keys are counted in eight tables (at most 256 keys, 16 elements per key) and, with at most 16, placed by swaps at any length, as each step of a cycle would wait on the step before it in the same few holes (2–3 times faster with four distinct keys up to 10,000 elements, 1.5 times beyond).
• Input mostly in order, and ranges of two keys per element or more, walk the places rather than the holes: the cycles start from each place in turn, with no loop per hole whose end mispredicts (3.5–4.5 times faster on nearly sorted input from 100 elements on); when the first keys are mostly in order they are also counted four at a time, so that a run of equal keys waits for memory once per four (twice as fast with sixteen keys per hole).
• Holes move instead of keys: pigeonhole_by_key rewrites each key, as it counts it, as its hole in the fewest bytes that hold every hole of the range (1.2–1.8 times faster at 10,000 elements).
• Holes are counted in u16 up to 65,535 elements, the next free place of each hole needs no clearing, and a range of more than 32 keys per element skips its empty holes eight at a time (1.1–2.2 times faster on a few elements over a wide range).
• Dense ranges walk their holes in a plain loop with no branch on whether a hole is empty, which mispredicts where about a third of them are.
• No allocation for small sorts: keys and counts of up to 4 KiB each live on the stack.

Examples

Rust usage with integers:

use a::sort::pigeonhole;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
  pigeonhole(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

Sorting by a key, in place (elements with equal keys may come in any order):

use a::sort::pigeonhole_by_key;

fn main() {
  let mut v = vec![(3, 'a'), (1, 'b'), (0, 'c'), (2, 'd')];
  pigeonhole_by_key(&mut v, |&(k, _)| k);
  assert_eq!(v, vec![(0, 'c'), (1, 'b'), (2, 'd'), (3, 'a')]);
}

Efficiency

• Time complexity:
  • Worst, average and best: O(n + k) for k possible keys between the smallest and the largest
  • Sorted and reverse-sorted input (also non-increasing for pigeonhole_by_key): O(n), one scan
• Moves: each element at most once along the cycles, or twice by swaps for large slices and few distinct keys; none for elements already in their holes
• Calls to key (pigeonhole_by_key): exactly n
• Space complexity: O(k) counts for pigeonhole; O(n + k) for pigeonhole_by_key (a buffer of n keys, rewritten as holes, and the counts), with no buffer for the elements; each on the stack up to 4 KiB, otherwise allocated once
• Stability: not stable (pigeonhole cannot tell equal keys apart anyway)
• Against the textbook pigeonhole sort (a vector per hole, the elements pushed in and read out): 2–6 times faster on random keys and 160–340 times on sorted u32 input
• Against the standard library, from 100 elements on: pigeonhole is 1.15–2.2 times faster than slice::sort_unstable on random u32 keys in a range of about n keys from 1000 elements on and 4–7 times on nearly sorted input, between 1.25 times faster and 1.2 times slower on a range of 4n keys, and as fast to 1.17 times slower with four distinct keys; pigeonhole_by_key is 1.05–2.8 times faster than slice::sort_unstable_by_key on random u64 keys of 16-byte elements up to 10,000 elements (1.35–1.45 times beyond), 1.7–5 times for 72-byte elements and 2–16 times on nearly sorted input, but 1.2–2.1 times slower on sorted and reverse-sorted input and 1.1–1.3 times slower with four distinct keys of 16-byte elements. Counting sort's stable counting_by_key, which moves the elements through a buffer, is 1.15–3.1 times faster on random keys; pigeonhole_by_key is 1.2–2.35 times faster on nearly sorted input of 72- and 128-byte elements, and needs no buffer for them

Tree

Tree sort is a stable, O(n log n) sorting algorithm that inserts the elements one by one into a binary search tree, in which the left subtree of every node holds the elements that go before it and the right subtree those that go after, and then reads the tree out in order (an in-order traversal) back into the slice. Binary search trees, and sorting by building one, go back to around 1960 (Windley; Booth and Colin; Hibbard). A plain binary search tree is only as good as the order the elements come in: sorted input builds a list and costs n²/2 comparisons. This implementation keeps the tree an AVL tree (Adelson-Velsky and Landis, 1962), the first self-balancing binary search tree: the two subtrees of every node differ in height by at most one, restored after each insertion by at most one single or double rotation, so the tree stays below 1.44·log₂ n levels and every insertion costs O(log n) whatever the input. An element equal to one already in the tree goes to its right, after it, which makes the sort stable. AVL trees were measured against red-black trees, whose looser balance makes them up to twice as high: within 10% of each other on random input, but red-black trees were 1.15–2.4 times slower on sorted, nearly sorted and sawtooth input and on input with few distinct keys. This implementation uses seven optimizations:

• One array of nodes instead of an allocation per node: node i belongs to the element that started at index i, so the nodes form one array with 32-bit indices as links and the balance factors in a separate byte array that only rebalancing reads; searches and the in-order traversal are loops with an explicit stack. Elements are moved twice and only twice, whatever the input. Against the textbook AVL tree sort, which allocates a node per element and inserts recursively, this alone (the crate's first version of this sort) is 1.2–4 times faster on random input and up to 30 times on sorted strings.
• Small elements live in the nodes: elements of 5 to 8 and of 17 to 24 bytes are copied into nodes of 16 and 32 bytes, so a search step loads a node and its key from one place; other elements stay in the slice, where they are compared, and are gathered into a buffer in order at the end (their nodes would waste a quarter or more on padding, and elements of up to 4 bytes or of 16 bytes are addressed by a shift in the slice too). This is 1.03–1.07 times faster on random input of 10,000 elements and more.
• Branchless search steps: a step loads both links of a node with its key and the comparison selects one, instead of a branch that random input mispredicts half the time or a load that waits for the comparison: 1.02–1.11 times faster up to 10,000 elements.
• Searches side by side: a search is a chain of dependent loads and comparisons that the processor cannot overlap with itself, so the places of the next 2 elements (4 from 1024 elements on, 8 from 262,144 on) are searched for at once in the same tree, and the elements are then inserted one after the other, in order. An insertion can only invalidate a later search through the slot it takes or a node it rotates; such a search goes on from the deepest node of its path still in place, usually a level or two above its slot, so the tree is exactly the one that one-by-one insertion builds, at up to 2% more comparisons with few distinct keys. On random input this is 1.1–3.7 times faster than one search at a time (most for strings and large slices), and 1.03–1.6 times with 16 distinct keys, except for 64-byte elements at 1,000,000 (1.08 times slower). Searching again from the root instead of going on is 1.05–1.2 times slower with few distinct keys.
• Insertion beside the last insertion: if the last element inserted went right after or right before the one inserted before it, the next one is first tried right after or right before it in turn. Two comparisons, with the last element and its neighbour in order, say whether it belongs there; the path to that slot is the last element's, kept up to date through the rotations, so no search is needed. Sorted, reverse-sorted and all-equal input costs n−1 comparisons, and an ascending or descending run costs two per element after its first, wherever it lands. This is 1.9–8 times faster on sorted and reverse-sorted input and 1.6–3.6 times on nearly sorted input, at up to 5% on random input.
• Short shifts of the kept path inline: a rotation removes a node from the path to the last insertion, usually a level or two above it; moving the one or two entries below it inline instead of calling memmove is 1.1–1.3 times faster on sorted and reverse-sorted input.
• No allocation for small slices: up to 4 KiB of nodes (240 nodes of 8-byte elements) live on the stack, which is 2.1–3.4 times faster for 2 elements, 1.1–1.4 times for 10 and up to 1.27 times for 30; beyond, nodes, balance factors and the gather buffer take one allocation.

Together, against the textbook tree sort, which builds an unbalanced binary search tree with a node allocated per element: 1.5–4.4 times faster on random input of 100 to 1,000,000 elements, and 1,600–2,500 times on 10,000 sorted elements, where the textbook sort makes n²/2 comparisons.

Examples

Rust usage with integers:

use a::sort::tree;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
  tree(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

Rust usage with strings:

use a::sort::tree;

fn main() {
  let mut words = vec!["pear", "apple", "fig"];
  tree(&mut words);
  assert_eq!(words, vec!["apple", "fig", "pear"]);
}

Equal keys keep their original order (cards are compared by rank only):

use a::sort::tree;
use std::cmp::Ordering;

#[derive(Debug, PartialEq, Eq)]
struct Card(u8, char);

impl Ord for Card {
  fn cmp(&self, other: &Self) -> Ordering {
    self.0.cmp(&other.0)
  }
}

impl PartialOrd for Card {
  fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    Some(self.cmp(other))
  }
}

fn main() {
  let ranks = [3, 1, 3, 0, 1, 3, 0, 2, 1, 0];
  let mut cards: Vec<Card> = "abcdefghij".chars().zip(ranks).map(|(c, r)| Card(r, c)).collect();
  tree(&mut cards);
  let order: String = cards.iter().map(|c| c.1).collect();
  assert_eq!(order, "dgjbeihacf");
}

Efficiency

• Time complexity:
  • Worst: O(n log n)
  • Average: O(n log n)
  • Best: O(n), when every element goes right after or right before the one before it (sorted, reverse-sorted or all-equal input)
• Comparisons:
  • Best (sorted, reverse sorted, all equal): n−1
  • Runs: at most 2 per element, plus a search for the first element of each run
  • Random input: about n·log₂ n − 1.2n (≈ 8,730 for n = 1000, against ≈ 10,000–11,000 for the textbook tree sort, which makes 499,500 on sorted input)
  • Worst: O(n log n), since a search takes fewer than 1.44·log₂ n steps, the height of an AVL tree, on any input
• Moves: exactly 2n, whatever the input (into the nodes and back, or gathered into a buffer and copied back)
• Space complexity: O(n) extra: a node of 8 bytes per element (16 or 32 bytes with the element inside) and a balance factor, on the stack up to 4 KiB and allocated once beyond, plus a buffer of n elements for elements that stay in the slice; O(log n) stack
• Stability: stable (equal elements keep their relative order)
• Adaptivity: adaptive to runs, which cost at most two comparisons per element. A binary search tree is a poor way to sort what fits in an array, though: every search step in a large tree is a cache miss and every insertion pays for rebalancing. slice::sort is 1.5–5 times faster on random input, 2–17 times with few distinct keys and 6–30 times on sorted input; this crate's Merge and Tim sorts are 1.25–4.5 times faster on random integers and 64-byte elements, and on random strings Merge sort is 1.3–1.8 times faster and Tim sort 1.05–1.4 times. Tree sort moves every element exactly twice, against n·log₂ n times for a merge sort, and is up to 1.9 times faster than slice::sort on nearly sorted strings and 1.4–1.5 times on nearly sorted 64-byte elements

Cycle

Cycle sort, described by B. K. Haddon in 1990, is an unstable, in-place sorting algorithm that writes to the slice as few times as any sort can. The permutation that sorts the slice splits into cycles (the element in slot a belongs in slot b, the one in b in c, and so on back to a), and each cycle is rotated once: the element of the cycle's first slot is taken out, its final slot is found by counting the elements smaller than it, it is written there and the element it displaces is taken in turn, until the element in hand belongs in the first slot. Equal keys share a block of slots, and an element goes to the first slot of its key's block that does not already hold an equal element. Every element is written at most once, straight into its final slot, and an element whose slot already holds its key is not written at all, which is the point where writes are slow or wear the memory out (flash, EEPROM). The price is the counting: Θ(n²) comparisons on any input that is not in order already. This implementation writes the same elements to the same slots as the textbook version (in the same order, except on strictly decreasing input) and uses six optimizations:

• Written cycle starts are passed over: after a cycle, the textbook takes the next slot as the next cycle start and counts for its element even if an earlier cycle wrote it, though such an element is final and the count finds nothing smaller. That is a third of all comparisons on random input (about 0.5n² of 1.5n²). A 4 KiB bitmap on the stack (a window of 32,768 slots) remembers the written slots: 1.23–1.25 times faster on 100 random u64s, 1.45–1.5 times from 1000 on and for strings and 64-byte elements, 1.15–1.25 times with four distinct keys from 1000 elements on. On nearly sorted input it gains nothing, and its bookkeeping (about 40 ns a sort) makes 100 u64s 1.08 times slower.
• Runs of written starts are passed over at once: a written start is recognised by its bit with a branch, and the whole run of written slots after it is passed over a word at a time (1.03–1.04 times faster on 100 u64s than one bit per start; scanning the bits from every start with no branch made each count wait and was up to 1.3 times slower on nearly sorted input).
• Sorted and reverse-sorted input is recognised: a non-decreasing slice is left alone and a strictly decreasing one is reversed, which writes the same elements to the same slots as the cycles would, at n−1 or n comparisons instead of Θ(n²) (18–460 times faster from 100 to 3000 elements; usually two comparisons on other input).
• The element in hand: the textbook in safe generic Rust keeps the element being placed in the cycle's first slot and swaps, writing that slot again at every step; here the element is moved out once and the first slot stays vacant until the cycle closes, so each element placed costs exactly one write (a guard puts the element back if a comparison panics). The speed is the same, within 4%.
• Long runs of equal small elements are skipped 16 at a time: for elements of up to 8 bytes, after 32 equal elements one at a time, they are compared 16 at a time in a few vector instructions (1.06 times faster on 1000 u64s with four distinct keys, 1.17 times on 3000; at most 1.06 times slower on 200–300 of them).
• Narrow elements are counted in counters as narrow as they are: the counts compare every element with no branch on the answer, so integers are compared several at a time, but into a usize the compiler widened the answer of every 1-, 2- and 4-byte element to 64 bits, two elements per vector instruction. Counting them into u8, u16 or u32 counters, added to the total every 192 elements for u8 and every 32,768 for the others, compares 16, 8 or 4 at a time: on random input 2.6–3.3 times faster for u32 from 1000 elements on, 4.1–6.6 times for u16 and 3.9–5 times for u8 (1.3–1.65 times on 100 elements), and 2.2–5.2 times with four distinct keys.

Examples

Rust usage with integers:

use a::sort::cycle;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
  cycle(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

Only the elements in the wrong slot are written (here the 0 and the 2):

use a::sort::cycle;

fn main() {
  let mut v = vec![2, 1, 0, 3];
  cycle(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3]);
}

Efficiency

• Time complexity:
  • Worst: O(n^2)
  • Average: O(n^2)
  • Best: O(n), when the input is non-decreasing or strictly decreasing
• Comparisons:
  • Non-decreasing input: n−1; strictly decreasing: n
  • Random distinct keys: about n² (the textbook cycle sort: about 1.5n²); with duplicates, placing an element also compares it with the equal elements already in its key's block
  • Worst: Θ(n²)
• Writes: exactly one per element whose slot does not already hold its key, and none for any other element: the fewest any sort can make (at most n; none for sorted input, 2⌊n/2⌋ for strictly decreasing input)
• Space complexity: O(1): a 4 KiB bitmap on the stack, no allocation (in-place)
• Stability: unstable (equal elements may be reordered)
• Against the textbook cycle sort: 1.2–1.3 times faster on 100 random u64s, 1.45–1.5 times from 1000 on and on random strings and 64-byte elements, 1.15–1.45 times with four distinct keys from 1000 elements on, 11–7000 times on sorted and reverse-sorted input, and as fast on nearly sorted input from 1000 elements on; on up to 200 nearly sorted u64s the textbook is 1.08–1.2 times faster, and on 100 u64s with four distinct keys 1.04 times. Elements of at most 4 bytes gain another 2.6–6.6 times from 1000 elements on (see above)
• Against Selection sort (at most n−1 swaps, so up to 2(n−1) writes): 2–2.6 times faster on random u64s and 4–5.1 times on nearly sorted ones; but selection sort is 1.1–2.3 times faster on random strings and 64-byte elements, 1.05–1.2 times on nearly sorted ones and 1.6–2.5 times on sawtooth ones, and, as it gathers equal keys in each pass, 2.25–700 times faster with four distinct keys
• Against the standard library: quadratic, so only worth it where a write costs far more than a comparison; slice::sort_unstable is 3–6 times faster on 100 random elements, 12–50 times on 1000 and 90–200 times on 10,000 (125 times on 3000 strings; 17–30 times on 5000 random u32s, u16s or u8s), and as fast on sorted and reverse-sorted input

Bitonic

Bitonic sort, published by Kenneth Batcher in 1968, is a sorting network: a fixed sequence of compare-exchanges, each putting the elements at two given positions in order, chosen in advance and never depending on what the comparisons answer. A sequence that first rises and then falls is bitonic; one stage of compare-exchanges, of each element of the first half with the element half a slice further on, splits it into two bitonic halves with nothing in the first greater than anything in the second, and repeating this on the halves merges it. Bitonic sort sorts the two halves in opposite directions, which makes the whole slice bitonic, and merges it: n·k·(k + 1) / 4 compare-exchanges for n = 2^k, in k·(k + 1) / 2 stages whose compare-exchanges are independent of each other, which is why it suits hardware, vector units, GPUs and threads. Batcher's network is for powers of two; for other lengths this is H. W. Lang's formulation (the first ⌊n/2⌋ elements sorted descending, the rest ascending, and the merge of n elements comparing i with i + m for m the largest power of two below n), which is the network of the next power of two without the compare-exchanges that would involve missing elements, so nothing is padded and any T can be sorted. It is unstable and in place, and not adaptive: every input of a length gets the same compare-exchanges. It comes in two forms: bitonic on the calling thread, and bitonic_parallel, which makes exactly the same compare-exchanges on several threads. This implementation uses five optimizations, all of which change only how the network is carried out, never which compare-exchanges it makes:

• Small networks in straight-line code: sorts of at most 16 elements and merges of at most 16 run their network with every compare-exchange written out at constant positions, so small elements stay in registers (2.2–4.2 times faster for integers than recursing down to single elements, 1.6–2 times for strings, 1.35–1.6 times for 64-byte elements; 1.9–2.4, 1.1–1.15 and 1.35–1.55 times faster than a loop over the same networks).
• Two or three stages per pass: a merge of a power-of-two length runs its first two or three stages as one pass over groups of 4 or 8 elements, each read once, put through the 4 or 12 compare-exchanges of those stages and written once, then merges its parts depth first, so the later stages run in cache (three stages make integers 1.04–1.14 times faster, two make 64-byte elements 1.03–1.08 times faster; strings, whose comparisons cost more than the passes, take one).
• Compare-exchanges without branches: elements of at most 8 bytes are exchanged by selecting the values to write back, which lets the compiler run a pass's independent compare-exchanges in vector registers (4.6–5 times faster than branching). Within a merge, whether a compare-exchange swaps comes in long runs, but in the small networks it is a coin toss on random input, so elements of 9 to 24 bytes, such as String, are exchanged there by selecting the addresses to copy from and by a branch in the passes (1.25–1.45 times faster for random strings, 1.05–1.1 times for nearly sorted ones; u128 and pairs gain 1.4–1.9 times on random input but lose up to 1.8 times on nearly sorted input, and arrays, whose comparison is itself a chain of branches, lose up to 1.4 times). Larger elements branch.
• The direction is a type: each part is sorted ascending or descending through a type parameter rather than a flag, so every compare-exchange is compiled for its direction.
• Narrow elements are merged stage by stage: for elements of at most 4 bytes, a merge of a power-of-two length of at most 2048 runs its stages one after the other, each as one loop over the whole merge, which stays in the first-level cache, so that every stage, down to the one pairing neighbours, runs as vector minimums and maximums of 4 to 16 elements at once instead of the one pair at a time of the straight-line merges of 16 (1.25 times faster for u32, u16 and u8 at 1000 elements, 1.45–1.6 times at 16,384 and 1.3–1.55 times at a million, on every input; for u64, two to a vector, it was 1.1–1.25 times slower).

bitonic_parallel uses one thread per 16,384 elements of at most 8 bytes, or per 4,096 larger elements, up to std::thread::available_parallelism; shorter slices are sorted by bitonic, with no allocation. It cuts the slice into parts along the sort's own halving, two or four per thread, sorts them in a first round, and then takes two rounds per level of merges: the first runs the stages that compare elements of different parts, one range of positions at a time across all parts, the second merges each part on its own. The threads are spawned once and kept for all rounds (spawning them for each round instead was 1.15–1.6 times slower from 32,768 to 131,072 elements, and 1.2 times for a million integers), take the tasks of a round, which touch disjoint elements, one at a time until none is left, and meet at a barrier between rounds. A panic on any thread lets the others finish their current tasks, skips the rest and is propagated to the caller, with every element still in the slice exactly once.

Examples

Rust usage with integers:

use a::sort::bitonic;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
  bitonic(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
}

Rust usage with strings:

use a::sort::bitonic;

fn main() {
  let mut words = vec!["pear", "apple", "fig"];
  bitonic(&mut words);
  assert_eq!(words, vec!["apple", "fig", "pear"]);
}

On all cores (the same compare-exchanges, so the same result, equal elements included):

use a::sort::bitonic_parallel;

fn main() {
  let mut v: Vec<u64> = (0..1_000_000).map(|i| i * 7919 % 1_000_003).collect();
  bitonic_parallel(&mut v);
  assert!(v.windows(2).all(|w| w[0] <= w[1]));
}

Efficiency

• Time complexity:
  • Worst, average and best: O(n log² n), the same on every input
  • Parallel: k·(k + 1) / 2 stages of independent compare-exchanges for 2^(k−1) < n ≤ 2^k, O(log² n) with enough processors
• Comparisons: exactly the network's, on every input: n·k·(k + 1) / 4 for n = 2^k, between n·(k − 1)² / 4 and n·k·(k + 1) / 4 for 2^(k−1) < n < 2^k (26,984 for n = 1000 against about 10,500 for Heap sort, 14,600 for elements of at most 8 bytes; 102,931,040 for n = 1,000,000, about 5.2·n·log₂ n)
• Space complexity: O(log n) stack, no allocation (in-place); bitonic_parallel allocates its list of tasks and its threads
• Stability: unstable (equal elements may be reordered)
• Adaptivity: none; sorted input costs as much as random input
• Against the textbook bitonic sort (Lang's recursion, with the direction as a flag and a branch and a swap for each compare-exchange): 10.5–11.8 times faster on random integers and 4.8–9.8 times on other input, 1.75–2.1 times on random strings and 1.3–1.6 times on other strings, 1.4–1.8 times for random 64-byte elements and 1.05–1.5 times on other input
• Against the standard library: as fast as slice::sort_unstable on random integers around 1000 elements (and 1.25 times faster than Quick sort), but its log₂ n factor shows from there on: sort_unstable is 1.35 times faster at 16,384 integers and 1.85 times at a million, 20–70 times faster on sorted input (random u32s and u16s, merged stage by stage, are sorted 1.1–1.3 times faster than by sort_unstable from 1000 to 16,384 elements and 1.25–1.45 times slower at a million), 2.5–5 times faster on random strings and 2.3–4.1 times for random 64-byte elements. Against Shell sort: 2.25–3.6 times faster on random integers from 1000 elements to a million, as fast on random strings, 1.35–1.6 times slower for 64-byte elements
• bitonic_parallel on the 16 threads of an Apple M4 Max (12 performance and 4 efficiency cores), against bitonic: integers 1.6 times faster at 32,768 elements, 2.5 times at 65,536, 2.9–3.2 times up to 262,144, 7.2 times at a million and 8.8 times at four million; strings 1.8 times faster at 8,192 elements, 3.3 times at 16,384, 4.4–5.7 times at 32,768 and 10–11 times from 262,144 on; 64-byte elements 1.7 times faster at 8,192 elements, 2.9 times at 16,384 and 8–9.7 times from 262,144 on (between 262,144 and a million integers, 8 to 12 threads would be up to 1.25 times faster than 16, as each round waits for its slowest thread). Against the single-threaded slice::sort_unstable it is faster from 32,768 elements on: for integers 1.2 times there and 3.9 times at a million, for strings 1.15 and 2.2 times, for 64-byte elements 1.05 and 2.4 times. The stage-by-stage merges make bitonic_parallel 1.05–1.25 times faster for u32 and 1.15–1.35 times for u8 from 65,536 to a million elements

Odd-Even

Odd-even sort, also called brick sort or odd-even transposition sort, is a simple, stable, in-place sorting algorithm that compares neighbours in alternating phases: an odd phase compare-exchanges the pairs (1, 2), (3, 4), …, and an even phase the pairs (0, 1), (2, 3), …, swapping a pair if its second element is smaller. An odd and an even phase make a round, and the textbook version repeats rounds until one swaps nothing. No two pairs of a phase share an element, so all compare-exchanges of a phase are independent: the algorithm comes from parallel computing, where a row of processors that only talk to their neighbours sorts n elements in n phases (Habermann, 1972). On one processor it is bubble sort with each pass cut into independent pairs; odd_even_parallel runs it on several threads. This implementation uses seven optimizations, none of which changes which compare-exchanges run in which phase (every swap is one the textbook version makes):

• Bounds from the last swaps: a pair that is in order stays in order until one of its elements changes, so the odd phase of a round only compares the pairs from one before the first to one after the last pair the previous even phase swapped, and the even phase one pair more at each end; the textbook compares all n−1 pairs every round. This saves 7% of the comparisons on 1000 random elements, makes nearly sorted input 1.25–1.8 times faster and input with few distinct keys 1.2–1.4 times, and an element out of place at either end (a turtle or a rabbit) costs about 3.5n comparisons instead of about n²/2.
• At most ⌈n/2⌉ rounds: n phases sort any input (the 0-1 principle), so the sort stops then even if the last round swapped. This saves the textbook's final round on input that needs every phase, such as reverse-sorted input, and guarantees that the sort ends with an inconsistent Ord, whose answers would otherwise almost never let a round pass without a swap.
• One sweep per round: the even pair (k, k+1) depends only on the odd pairs on either side of it, so one sweep compares an odd pair and then the even pair just behind it — a wavefront making the same compare-exchanges on the same elements as two separate phases, while loading each element once per round instead of twice: 2–2.2 times faster for integers, up to 1.7 times for strings and 1.6 times for 64-byte elements.
• Branchless compare-exchanges for elements of at most 8 bytes: both elements are read and the smaller and the larger written back, chosen by the comparison, so that a chunk of 32 odd and 32 even pairs compiles to vector code for integers and reports its swaps as a bit mask. 1.3–2 times faster than branching on random input or few distinct keys (2–10% slower on nearly sorted input, where branches are predictable); 16-byte elements are 2.4–3.9 times slower without branches, so larger elements keep them.
• Elements of at most 4 bytes split into even and odd positions: a chunk of 32 steps is moved out of the slice into two small arrays, one for the elements at even positions and one for those at odd ones, and back after both phases, with the element where the next chunk starts carried over in a register. Every pair of a phase then sits at the same place of the two arrays (one place apart for the odd phase), and the compiler runs each phase as a few vector minimums and maximums, where in the slice it picked lanes apart and widened every swap bit to 64 bits. The same pairs are compared and the same swaps made (the elements are compared where the chunk holds them, outside the slice): 1.3–1.5 times faster for 4-byte elements from 1000 elements on, 1.7–2.35 times for 2-byte and 3.3–4.3 times for 1-byte ones (1.05–1.5 times on 100); for u64 it made no difference.
• For larger elements, swaps by plain copies with the even phase two pairs behind the odd one: mem::swap compiled to copies the processor could not forward to the next comparison (1.2–1.9 times slower for 16- and 64-byte elements), and an even phase right behind the odd one was 1.07–1.45 times slower for 64-byte elements.
• Parallel form: odd_even_parallel cuts the slice into blocks that threads (std::thread::scope, no dependencies) claim in turn; on its block a thread runs a super-step of K phases, each leaving out one more pair at each interior end (a trapezoid), and in the next super-step the slice is cut at the midpoints of the previous blocks, so that each thread first completes the triangle of pairs left out around one old boundary and then runs the next trapezoid. Every compare-exchange still runs exactly once, after the two it depends on, so this is still odd-even transposition sort (not block merge-split sort), with one barrier per super-step instead of one per phase. Short slices and input that is sorted within the first rounds never start a thread; a panic in any thread reaches the caller with its payload.

Examples

Rust usage with integers:

use a::sort::odd_even;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8];
  odd_even(&mut v);
  assert_eq!(v, vec![1, 2, 4, 5, 8]);
}

A turtle (the 0 at the end moves two slots per round, and each round only compares around it):

use a::sort::odd_even;

fn main() {
  let mut v = vec![1, 2, 3, 4, 5, 0];
  odd_even(&mut v);
  assert_eq!(v, vec![0, 1, 2, 3, 4, 5]);
}

On several threads:

use a::sort::odd_even_parallel;

fn main() {
  let mut v: Vec<u32> = (0..10_000).rev().collect();
  odd_even_parallel(&mut v);
  assert!(v.windows(2).all(|w| w[0] <= w[1]));
}

Efficiency

• Time complexity:
  • Worst: O(n^2)
  • Average: O(n^2)
  • Best: O(n), when the input is already sorted
  • Parallel: O(n^2 / p) work per thread on p threads, with one barrier per super-step
• Comparisons and swaps (I = number of inversions):
  • Any input: exactly I swaps (each removes one inversion), as the textbook version; never more comparisons than the textbook version
  • Best (sorted): n−1 comparisons, 0 swaps
  • Reverse sorted: n(n−1)/2 comparisons for even n, (n²−1)/2 for odd n, every one a swap; the textbook version makes n−1 more
  • Turtle [1, 2, …, n−1, 0]: (7n−16)/2 comparisons for even n, (7n−13)/2 for odd n, against (n−1)(⌊n/2⌋+1) for the textbook version (3,492 against 500,499 for n = 1000)
  • Random input: about 453,400 comparisons for n = 1000 (textbook ≈ 486,800) and about n²/4 swaps
• Space complexity: O(1) extra (in-place); the parallel form allocates only for its threads and a block plan
• Stability: stable (only neighbours are swapped, and only when the second is strictly smaller)
• Adaptivity: the bounds shrink to the part still changing; good for nearly sorted input whose displaced elements have not far to go, but a far-displaced element still costs a phase per slot
• Against the textbook version (1000 and 5000 elements): 1.15–3.4 times faster for integers (2–2.6 on random), 1.03–1.75 times for strings, 1.0–2.1 times for 64-byte elements; elements of at most 4 bytes gain another 1.3–4.3 times from splitting chunks into even and odd positions
• Against Bubble: 1.6–1.7 times faster on random integers, but on strings and 64-byte elements from 1.1 times faster to 2 times slower (bubble sort shifts an element with one write per slot instead of swapping). Against Cocktail Shaker: 1.45 times faster on random integers and 2.1 times on few distinct keys, but 1.2–1.4 times slower on random strings, 1.5–2.2 times on 64-byte elements and 20–50 times on nearly sorted input, which cocktail shaker sort fixes in a few passes
• Against slice::sort_unstable: about 20 times slower on 1000 random integers and 85 times on 5000 (on random u32s about 11 and 45 times, on u8s 8 and 30 times) — prefer slice::sort for real workloads
• Parallel form against the sequential one (16-core machine, 12 performance cores, under other load): 4.3–6 times faster on 20,000 integers, 7–8 times on strings and 6.6–10.5 times on 64-byte elements; 1.9–3.8, 4.4–6.5 and 3.5–6.6 times on 8192; 1.3–2.1, 2.7–4 and 2–4.4 times on 4096. It uses threads from 4096 elements of at most 8 bytes and 2048 larger ones, after the first 64 rounds (or 2²⁰ / 2¹⁶ compared pairs) on the calling thread. Splitting chunks into even and odd positions makes it 1.2–1.25 times faster for u32 and 2.1–2.2 times for u8 on 8192 and 20,000 elements

Stooge

Stooge sort is a deliberately slow, unstable, in-place sorting algorithm, mostly of educational value: an example of a short, correct algorithm with a surprising running time. It compares the first and the last element and swaps them if they are out of order; then, if the slice has at least three elements, it stooge-sorts the first two thirds (rounded up), the last two thirds, and the first two thirds again. The first call moves every element of the largest third that starts in the first two thirds into the middle, so after the second call all of them sit at the end, in order, and the third call sorts the rest. It is Problem 7-3 of Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms, where Professors Howard, Fine and Howard (the Three Stooges) propose it as an "elegant" sorting algorithm, and the reader shows that it takes Θ(n^{(log 3 / log 1.5)) ≈ Θ(n}2.71) time, worse than bubble sort. Which elements are compared depends only on the length of the slice, never on the answers: stooge sort is a sorting network, one fixed sequence of compare-exchanges for each length. This implementation makes exactly the textbook's comparisons, in the same order, with the same swaps, and uses three optimizations in executing them:

• Unrolled bottom levels: all parts at one depth of the recursion have the same length, so the parts four levels above the bottom have 7, 8 or 9 elements throughout one sort; they run as straight-line code, the 121 compare-exchanges below them at constant indices, with no calls and no index checks. The textbook makes one call per compare-exchange, and the calls are its cost: recursing down to two elements without index checks is only 1.05–1.15 times faster than it, while unrolling four levels is 5–8 times faster for u64, 1.4–1.65 times for strings and 1.4–2.3 times for 64-byte elements than recursing down to two elements.
• A branch, not a branchless select: only about 1% of the compare-exchanges swap anything (4.5% at 16 random elements, 0.2% with few distinct keys), so the branch is predicted almost always and the compare-exchanges do not wait for one another; a branchless select, which chains each to the one before, was 2 times slower than the textbook for u64, 4 times for strings and 1.8 times for 64-byte elements.
• The swap is marked cold, so the compare-exchanges that do not swap are laid out as one straight line: 1.5–1.85 times faster for 64-byte elements, 1.05–1.25 times for strings and 1.1–1.25 times for u64 from 100 elements on.

The code is safe Rust, with no unsafe block.

Examples

Rust usage with integers:

use a::sort::stooge;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8, 0];
  stooge(&mut v);
  assert_eq!(v, vec![0, 1, 2, 4, 5, 8]);
}

Sorting strings:

use a::sort::stooge;

fn main() {
  let mut words = vec!["pear", "apple", "fig"];
  stooge(&mut words);
  assert_eq!(words, vec!["apple", "fig", "pear"]);
}

Efficiency

• Time complexity: Θ(n^{(log 3 / log 1.5)) ≈ Θ(n}2.71) on every input (worst, average and best alike)
• Comparisons: exactly C(n) = (3^(D+1) − 1)/2 on every input of n ≥ 2 elements, where D is the number of times m ↦ m − ⌊m/3⌋ takes n to 2 (equivalently C(2) = 1, C(n) = 1 + 3·C(n − ⌊n/3⌋)): 13 for n = 4, 121 for n = 8, 1,093 for n = 16, 265,720 for n = 100 (and for 128: D grows in steps), 64,570,081 for n = 1000, against at most n(n−1)/2 = 499,500 for bubble sort
• Swaps: at most C(n), depending on the input; about 1% of the comparisons on random input; none on already-sorted input
• Space complexity: O(log n) stack, no allocation (in-place); the recursion nests D − 4 levels for n ≥ 10 (12 for n = 1000)
• Stability: unstable ([1a, 1b, 0] becomes [0, 1b, 1a])
• Adaptivity: none; the same comparisons on every input of a given length
• Against the textbook stooge sort (recursive, one call per compare-exchange): 9–11 times faster for u64 from 64 elements on (3–10 times below), 1.7–2.2 times for strings, and 4.3–5 times for 64-byte elements from 32 on (2.5–4.5 times below; 1.4–2 times with few distinct keys, where every comparison reads all 64 bytes)
• Against the standard library: slice::sort_unstable is 1.2–4 times faster on 8 elements, 50–130 times on 100 random elements, 900–2400 times on 1000 and about 4000 times on 2000 random u64; on sorted input, which std recognises in one pass, 10,000–70,000 times from 500 elements on

Sleep

Sleep sort, posted anonymously to 4chan's programming board in 2011, is a joke: a shell script that started sleep $n; echo $n in the background for every argument n, so that the small numbers wake, and are printed, first. It sorts in "linear time", lets the operating system's timer queue do all the work, and is wrong as soon as the scheduler is late. sleep is that algorithm with real threads and real sleeping: one thread per element sleeps (value − min) × unit past a start all threads share, and the values are written back in the order their threads wake. Keys are the same as counting sort's (the sealed IntegerKey trait), so negative numbers, chars and bools work too, and the smallest values wake right at the start.

It is nondeterministic and intended as a curiosity. A thread scheduled late lets a larger value overtake a smaller one, so the slice may come out unsorted; sleep returns whether it did, true exactly when the slice ends up in order. Whatever happens, the slice ends up a permutation of what it was: every value is written back exactly once. It panics, leaving the slice as it was, if the clock cannot represent when the largest value would wake (about 292 billion years on Unix-like platforms: the whole range of i128 at a nanosecond per unit, or of u64 at a second; a zero unit never panics) or if the system cannot start a thread for every element (16,384 per process on macOS), after sending home the threads already started. A range the clock can represent is slept through, however long: the whole range of i64 at a nanosecond per unit takes 584 years. This implementation uses four optimizations, for faithfulness and robustness rather than speed (the success rates are for random keys in 0..n on a 16-core Mac loaded by other benchmarks):

• One shared start: every thread sleeps until start + (value − min) × unit, not for a duration from whenever it happened to be started, so the order and the cost of starting the threads (15 µs each for 1000 of them) do not skew when they wake. Sleeping from each thread's own start, 100 elements at 100 µs per unit and 1000 elements at 1 ms never came out sorted; from the shared start, almost always.
• The clock starts once every thread is running, and a little later: all threads are started first and wait at a gate, a RwLock the caller holds for writing, and the start is set 4 µs per thread after the gate opens, as waking the waiting threads takes the system 1.5–3 µs each. With the start at the gate, the smallest values, released last, woke after the next ones: 1000 elements at 100 µs never came out sorted (100 elements: 64%; 1000 at 1 ms: 30%).
• Sleeping in halves: the system may let a sleep run longer than asked, to wake several threads together (here 1 ms took 1.5 ms, 5 ms took 7.5 ms, 50 ms up to 60 ms). Each thread sleeps for half the time left until its deadline, again and again, and for all of it once less than 50 µs is left, so a late sleep still ends before the deadline and the last, short one is late by a few dozen microseconds at most. At 1 ms per unit: from 39% to 100% sorted for 10 elements, from none to all for 100, and from none to 60–95% for 1000. Spinning through the last microseconds instead was no better.
• Small stacks: each thread gets a 16 KiB stack instead of the default 2 MiB, which halves the time to start 5000 threads or more (0.27 s instead of 0.55 s for 5000).

The values are written back lock-free, each waking thread taking the next place from an atomic counter, and (value − min) × unit is computed in 128 bits, saturating at Duration::MAX.

Examples

Rust usage with integers (a unit of a few milliseconds almost always sorts a few values):

use a::sort::sleep;
use std::time::Duration;

fn main() {
  let mut v = vec![5, 1, 4, 2, 8, 0, 3, 9, 7, 6];
  let sorted = sleep(&mut v, Duration::from_millis(2));
  if sorted {
    assert_eq!(v, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
  } else {
    println!("the scheduler was late: {v:?}");
  }
}

Negative numbers sleep from the smallest one, and the return value always tells the truth:

use a::sort::sleep;
use std::time::Duration;

fn main() {
  let mut v = vec![3, -2, 0, -5, 1];
  let sorted = sleep(&mut v, Duration::from_millis(1));
  assert_eq!(sorted, v.is_sorted());
}

Efficiency

• Time complexity: (max − min) × unit of sleeping, plus starting n threads (about 15 µs each up to 1000 threads, more beyond: 0.27 s for 5000, 1 s for 10,000) and 4 µs per thread before the start, whatever the order of the input: "linear" in the range of the values, not in their number

• Comparisons: none between elements (one pass for the smallest and largest value, one to report whether the result is sorted)

• Threads: exactly n, one per element, all alive at once

• Space complexity: O(n): a 16 KiB stack per thread; the values move through no buffer

• Correctness probability (share of sorts that came out sorted, random keys in 0..n, over three runs of 20–400 sorts on a loaded 16-core Mac):

  unit	10 elements	100 elements	1000 elements
  10 µs	12–18%	0%	0%
  100 µs	94–100%	94–100%	89–100%
  1 ms	99–100%	89–100%	60–90%

  A unit of 10 µs is below what the timers resolve (a thread wakes 10–15 µs after its deadline at best); a longer sort is longer exposed to the other work of the machine, so 1000 elements at 1 ms (a second) came out sorted less often than at 100 µs (a tenth of that)

• Stability: equal values wake together, in any order, which cannot be seen

• Against the standard library: hopeless, of course. slice::sort_unstable sorts 1000 random u32s in 3.5 µs and 100 in 0.2 µs; sleep takes about 115 ms and 11 ms at 100 µs per unit, 30,000–55,000 times as long, and is not always right