Function quick 

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

Sorts a slice in place using quick sort.

Quick sort picks a pivot element, 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. With pivots near the median every level halves the parts, so the sort makes O(n log n) comparisons, and it needs no buffer.

Seven refinements keep the algorithm as cheap as quick 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.
• Pivots from a median of samples. The pivot is 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 (243 for a million elements). On random input this keeps comparisons at about n·log₂ n, 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, which defeats the branch predictor. Instead, every element is moved unconditionally, with the comparison only choosing where: a vacant slot cycles through the slice, and each element either joins the smaller part or moves to the end of the larger one (Lomuto’s scheme, made branchless). That costs two moves per element, which larger elements pay for more than a misprediction, so they are partitioned by Hoare’s scheme, which moves only misplaced pairs, two moves per pair by cycling them through a vacant slot instead of three by swapping. On random input the branchless scheme is 1.9–4.3 times faster than Hoare’s for integers and 1.4–2.5 times for strings.
• Runs of equal elements in one pass. If the pivot equals the pivot of the enclosing partition, which is no larger than any element of this part, the part is partitioned into elements not larger than the pivot, all equal to it and done, and the rest. Input with k distinct keys costs O(n log k), and all-equal input is never quadratic.
• Recursion into the smaller part only. The larger part is sorted by looping, 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 (fixed sequences of 1 to 19 compare-exchanges) made of branchless swaps, unrolled for each length so the elements stay in registers. On random input this makes integers sort 1.3–1.85 times faster than with insertion sort. Larger elements pay for a compare-exchange’s three moves, so their parts of at most 16 elements are sorted 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 no sampling rules out (an adversary that answers comparisons adaptively can force it). Such a part is finished by this crate’s heap sort, so no input makes the sort quadratic (the “introsort” idea).

Properties

• Unstable: equal elements may be reordered.
• In place: no allocation, O(log n) stack.
• Adaptive to sorted and reverse-sorted input, and to repeated keys.

Case	Comparisons	Moves
Best (sorted, reverse, all equal)	n − 1	0 (n reversed)
Average (random)	≈ n·log₂ n + (0.2–1)·n	≈ 2n·log₂(n/8)
k distinct keys	O(n log k)	O(n log k)
Worst	O(n log n)	O(n log n)

For n = 1000: 999 comparisons on sorted or reverse-sorted input and about 10,200 on random input (n·log₂ n + 0.22n); for n = 100,000 and n = 1,000,000, about n·log₂ n + 0.6n. Elements larger than 16 bytes, whose short parts are sorted by insertion sort, take up to 0.4n more.

On nearly sorted input (a few elements out of place), Hoare’s scheme would be 1.5–1.75 times faster for integers and 1.2–1.5 times for strings, since its branches are then predictable; on random input it is 1.9–4.3 times slower. slice::sort_unstable, which shares several of these ideas, is 1.1–1.2 times faster on random integers from 100 elements on (its short parts are merged through a buffer, which is only sound for types without interior mutability, something stable Rust cannot test for). 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.

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::quick;

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

// Many duplicates are handled in one pass per distinct pivot.
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]));

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