A

The A Library is a set of algorithms.

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

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 two common 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).

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.

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.

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 two 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.

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.

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 along each chain at small gaps, for elements of at most 8 bytes: at a gap of 8 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, each chain c, c + gap, c + 2·gap, … is walked holding the largest element seen so far in a register, writing back only the smaller of it and the next element: the same comparisons and the same result, with one move per swap plus one per carried element instead of two per swap. This makes the whole sort 10–50% faster for integers and pointers; for larger elements, whose comparisons usually read memory, it would be slower, because each comparison has to wait for the previous one.

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.2 times slower than slice::sort_unstable on 10,000 random u32 and 1.6 times on u64

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 five 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.
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.
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.
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 exactly 2⌊m/2⌋ comparisons after the two checks, and moves every element twice: out to the buffer and back):
- 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)
- Random input: about n·log₂ n − 0.35n comparisons (≈ 9,620 for n = 1000; 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 2n·log₂(n/8) + 2n moves
- Worst: at most n·log₂ n + O(n) comparisons
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); faster than slice::sort on slices of up to about 20 random integers, but about 1.75 times slower on 100,000 and 1.1 times on large elements, since the standard library's stable sort also finds natural runs and merges them more cleverly

nettrash-a 0.0.4

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