Function shell 

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

Sorts a slice in place using Shell sort.

Shell sort, published by Donald Shell in 1959, is insertion sort with a gap. A pass with gap h insertion sorts every chain of elements h apart, v[c], v[c + h], v[c + 2h], ..., 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, which the earlier passes leave with little to do. How fast the sort is depends almost entirely on the gap sequence: with the ones used here it makes about 1.6–2·n·log₂ n comparisons on random input of up to a million elements, though no gap sequence is known to make Shell sort O(n log n).

Five refinements keep the algorithm as cheap as Shell sort can be:

• 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. This costs n − 1 comparisons on such input and usually two or three on any other.
• 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 the three of a swap.
• 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 the fewest comparisons of the sequences tried, 1.1–1.27 times fewer than Sedgewick’s 1982 one (1, 8, 23, 77, 281, 1073, ...). But every pass ends nearly every insertion with a mispredicted branch, and Sedgewick’s gaps grow by a factor of about 4 instead of 2.25, 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, where each comparison is a cache miss). 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 that is still 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% and 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 of them it passes is computed as a number, and the 5 slots are rewritten from copies chosen by an index computed from that number: no branch, at the cost of comparisons that turn out unnecessary. Only the 8% of elements that pass all 4 go on with a branch per step. On random input this is 1.4–1.8 times faster for integers.
• The window only while it pays. On a slice that is nearly sorted, insertion’s branches are predictable and the window’s extra comparisons and writes are wasted: up to 2.6 times slower. So a pass takes the window only if the pass before it moved more than a quarter of the elements; the first pass assumes it did, and the final pass, with gap 1, never does, since each element there depends on the one just placed.

Properties

• Unstable: equal elements may be reordered (an insertion along a chain can carry an element past an equal one that lies between the two in the slice).
• In place: O(1) auxiliary memory, no allocation.
• Adaptive: the passes do less on nearly sorted input, and sorted or reverse-sorted input costs one scan.

Case	Comparisons	Moves
Best (sorted, reverse, all equal)	n − 1	0 (n reversed)
Average, Sedgewick’s gaps	≈ (1.6–2)·n·log₂ n	O(comparisons)
Average, Ciura’s gaps and window	≈ (2.1–2.8)·n·log₂ n	O(comparisons)
Worst	O(n^(4/3)), Sedgewick’s gaps	the same

No bound is known for Ciura’s gaps, which were found by experiment.

For n = 1000: 999 comparisons on sorted or reverse-sorted input and about 15,900 on random input, or 21,300 with the window, whose unnecessary comparisons are cheap for small elements; heap sort makes about 10,500.

Against classic Shell sort with Ciura’s gaps, plain insertion and the same scan for a run, this is 1.2–1.75 times faster on random integers, 1.1–1.65 times on nearly sorted ones and 1.15–1.3 times with few distinct keys; 1.05–1.4 times faster on strings except random ones from a million elements on, and 1.03–1.3 times on 64-byte elements. Against this crate’s comb sort, whose fixed compare-exchanges the compiler vectorizes for integers: 2.4–3.3 times slower on random integers from 1000 elements on, but faster on nearly sorted input and with few distinct keys up to 1000 elements, and 1.3–2.5 times faster on strings that are nearly sorted, have few distinct keys or follow a pattern. Against heap sort: 1.3–1.7 times slower on random integers from 1000 elements on, about as fast on random strings, and faster on everything nearly sorted or patterned.

Shell sort is mainly of educational value; prefer slice::sort_unstable 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: nothing is dropped twice or leaked. An Ord that is not a total order leaves arr in an unspecified order with every element exactly once as well.

Examples

use a::sort::shell;

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

// Small elements far from their place travel in long steps.
let mut v: Vec<u32> = (0..1000).rev().chain(1000..2000).collect();
v.swap(0, 1999);
shell(&mut v);
assert!(v.windows(2).all(|w| w[0] <= w[1]));

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