Function selection 

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

Sorts a slice in place using double-ended selection sort.

Each pass scans the unsorted middle of the slice once, finds both its smallest and its largest key, moves every element holding the smallest key to the front of that range and every element holding the largest key to its back. Those elements are then in their final places, so the next pass scans only what lies between them.

Three refinements keep the algorithm as cheap as selection sort can be:

• Pairwise min-max scan. Elements are taken two at a time: the two are compared with each other first, then only the smaller one is compared with the running minimum and only the larger one with the running maximum. A range of m elements costs ⌈3m/2⌉ - 2 comparisons per pass instead of the 2m - 2 of two independent scans, which is the fewest any algorithm can use to find both extremes.
• Duplicate gathering (“bingo”) for free. Every comparison is a three-way Ord::cmp, so an element equal to the running minimum or maximum is recognised without an extra comparison and joins that key’s group. A pass therefore retires all copies of two keys: input with k distinct keys finishes in at most ⌈k/2⌉ passes instead of ⌊n/2⌋. A pass in which every comparison reports Equal has proved the whole range equal and ends the sort, again at no extra cost. An equal pair also skips the comparison with the maximum whenever its minimum comparison already rules that out.
• Lazy placement. A running minimum or maximum that has no duplicate yet is only remembered by index; elements are moved once a pass is over, or when a second copy of the current extreme turns up. Input with distinct keys costs at most n - 1 swaps, exactly like classic selection sort, and gathering duplicates never costs a comparison.

Which element of a pair is the smaller one is a coin flip on random input, and a branch on it would be mispredicted every other pair. The scan therefore picks the element to compare with the minimum, and the one to compare with the maximum, without branching, and only branches on the rare outcomes that change an extreme: on random input with distinct keys that is 1.1–1.5 times faster at 64 elements and 1.7–2.5 times from 1,000 up, for integers, strings and 64-byte arrays alike. Choosing without a branch makes the next two comparisons wait for the first, which costs more than a predicted branch when comparisons are slow to start, as for strings in order: so for elements of 9 to 32 bytes the first pass branches and counts how often a pair goes against the majority order, and later passes branch only if fewer than one in 16 did. The comparisons are the same either way.

Distinct keys get no benefit from the refinements beyond the pairwise scan, so the worst case is any input with distinct keys, and on such input the number of comparisons depends only on n: n(3n - 2)/8 for even n and 3(n² - 1)/8 for odd n, about 25% fewer than the n(n - 1)/2 of classic selection sort.

Properties

• Not stable: equal elements may be reordered.
• In place: O(1) auxiliary memory, no allocation.
• Not adaptive to order: sorted input costs as much as any other with distinct keys. It is adaptive to duplicates instead: the fewer distinct keys, the fewer passes.

Case	Comparisons	Swaps
Best (all elements equal)	n - 1	0
k distinct keys	O(nk)	O(nk)
Worst (all keys distinct)	n(3n - 2)/8 or 3(n² - 1)/8	≤ n - 1

Gathering duplicates costs at most 2m swaps in a pass over m elements, so input with many repeated keys trades the n - 1 swap bound for far fewer comparisons and passes. Input that is already in non-decreasing order is never moved at all.

Selection sort is quadratic and 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: elements are only ever exchanged with slice::swap.

Examples

use a::sort::selection;

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

// Three distinct keys: the first pass retires every 1 and every 3, the second the 2s.
let mut v = [3, 1, 2, 3, 1, 2, 2, 1];
selection(&mut v);
assert_eq!(v, [1, 1, 1, 2, 2, 2, 3, 3]);

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