Function insertion 

pub fn insertion<T: Ord>(arr: &mut [T])

Sorts a slice in place using pair insertion sort with galloping search.

A sorted prefix grows from the left two elements at a time. The two new elements are ordered with one comparison, the larger one’s place in the prefix is searched for from the right, and the smaller one’s place is searched for only to the left of that, since it cannot lie anywhere else. Both then move into place together. This is the pair insertion sort that Java’s dual-pivot quicksort uses for short ranges, with a galloping search in place of its linear scan.

Three refinements keep the algorithm cheap:

• Sorted fast path. The smaller element of a pair is compared with the last element of the prefix before any search. If it is not smaller, neither is the larger one, and the pair is done after two comparisons, one per element: already-sorted input costs exactly n - 1 comparisons, as with plain insertion sort.
• Galloping search. An insertion point is found by probing 1, 2, 4, 8, … slots to the left of where the search starts, then binary searching the last gap. An element that moves d slots left costs at most 2⌊log₂ d⌋ + 2 comparisons: logarithmic in how far it moves rather than linear (a plain scan) or logarithmic in the length of the prefix (a binary search), so nearly-sorted input stays nearly linear.
• Pair moves. Prefix elements greater than both new elements shift right by two slots at once and those between them by one, and each new element is written once into its final slot. A prefix element that both new elements pass therefore moves once instead of twice. Both insertion points are found before anything moves, so no comparison ever runs while an element is out of the slice. Short moves of elements of up to 32 bytes are made in place, four elements at a time, rather than by a call to memmove, which costs them more than the copying.

Against inserting the same elements one at a time with the same galloping search, a pair spends one comparison on ordering itself, and in exchange the smaller element’s search starts from the larger one’s insertion point instead of from the end of the prefix, and the prefix elements past that point move once instead of twice. On 1000 elements, counting a move each time an element changes slot:

Input (n = 1000)	Comparisons, pair	one at a time	Moves, pair	one at a time
Sorted	999	999	0	0
Random, distinct (mean)	≈ 14,580	≈ 14,920	≈ 167,400	≈ 250,600
Reverse sorted	5,986	9,966	250,998	500,499
Worst case, per column	17,020	17,169	250,999	500,499

On random input the two searches of a pair together cost slightly less than two single ones, and a third of the moves are saved (≈ n²/6 against ≈ n²/4). On reverse-sorted input both halve: the larger element goes to the front, which leaves the smaller one nothing to search and every prefix element to pass only once.

Properties

• Stable: equal elements keep their relative order. A pair is reordered only when its second element is strictly smaller, and each element is inserted after every prefix element that is not greater than it.
• In place: O(1) auxiliary memory, no allocation.
• Adaptive: comparisons grow with the logarithm of how far elements move, moves with the distance itself.

Let dₓ be the number of elements before x in the input that are greater than x, which is how many slots x moves left, and I = Σ dₓ the number of inversions.

Case	Comparisons	Moves
Best (already sorted)	n - 1	0
Any input	≤ n - 1 + Σₓ 2⌈log₂(dₓ + 1)⌉	≤ I + n
Reverse sorted	≈ (n/2)·log₂ n + n	≈ n²/4 (the worst)
Worst	≤ 2n·log₂ n (≈ 2n·log₂ n - 3n)	≈ n²/4

The adaptive bound is tight: input such as [1, 0, 3, 2, 5, 4, ...] comes within two comparisons of it. By concavity it is below 3n + 2n·log₂(1 + I/n), so input with few inversions sorts in close to linear time. The worst case needs every element to move a long way, but not to the front, where a search is cut short. On reverse-sorted input, a pair inserted into a prefix of i elements costs exactly ⌈log₂ i⌉ + 3 comparisons and i + 2 moves, the most a pair can move (only the first pair, whose larger element ends in the slot it started in, moves two), and the last element when n is even costs ⌈log₂(n - 1)⌉ + 1 comparisons and n moves.

Insertion sort moves O(n²) elements on random input and is mainly of educational value beyond short or nearly-sorted slices; prefer slice::sort for real workloads.

Panics

Does not panic by itself. If the Ord implementation of T panics, the panic is propagated and arr is left in an unspecified order, but it still holds every original element exactly once: every comparison is made while all elements are in the slice, and the moves that follow cannot panic.

Examples

use a::sort::insertion;

let mut v = [5, 1, 4, 2, 8, 0];
insertion(&mut v);
assert_eq!(v, [0, 1, 2, 4, 5, 8]);

// Equal keys keep their order: sorting by the first field leaves 'a' before 'b'.
#[derive(Debug, PartialEq, Eq)]
struct Card(u8, char);
impl Ord for Card {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.0.cmp(&other.0)
    }
}
impl PartialOrd for Card {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}
let mut cards = [Card(2, 'a'), Card(1, 'x'), Card(2, 'b'), Card(0, 'y')];
insertion(&mut cards);
assert_eq!(cards, [Card(0, 'y'), Card(1, 'x'), Card(2, 'a'), Card(2, 'b')]);

let mut words = vec!["pear", "apple", "fig"];
insertion(&mut words);
assert_eq!(words, ["apple", "fig", "pear"]);