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 4 slots it can move into are rewritten from copies held in registers, each chosen by two selects on 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.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. How many elements move does not tell the two apart (sawtooth input moves as many as random input), 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, it counts the runs of consecutive elements that moved and the steps they took beyond the first, and takes 2·runs + 0.35·steps > 0.42 per element as unpredictable; through the window, it counts how often the number of elements passed differs from the one before, and takes more than 0.42 per element as unpredictable. 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. The first pass assumes the window pays, and the final pass, with gap 1, never takes it, since each element there depends on the one just placed. Against taking the window whenever the pass before moved more than a quarter of the elements, this is 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 (within 3%; sorted runs of about √n random elements, which only the old count read right, are 1.03–1.25 times slower below 10,000 elements).

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.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 it ranges from 1.15 times slower (a period of 16 at 1000 elements, which the branch predictor learns from history the window cannot see) to 1.35 times faster, mostly within 1.1 times either way; 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: 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.

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"]);