Function bubble 

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

Sorts a slice in place using bubble sort.

Each pass walks the unsorted prefix from left to right, carrying the largest element seen so far towards the end until it meets an element that is not smaller than it. After a pass, everything from the position of the last move onwards is in its final place, so the next pass stops there; a pass that moves nothing ends the sort.

Four refinements keep the algorithm as cheap as bubble sort can be:

• Last-move tracking. The next pass scans only up to the last element that moved, so already-sorted input finishes after a single pass of n - 1 comparisons and partially sorted tails are never rescanned.
• Hole shifting instead of swapping. An element travelling k slots to the right is read once, the k smaller elements are each shifted left by one, and the element is written once into its final slot: k + 1 moves instead of the 3k moves of k swaps.
• Branchless passes for small elements. Whether a comparison starts or ends a carry is hard to predict on most inputs, and each misprediction costs as much as a dozen comparisons. For elements of at most 8 bytes with no drop glue (integers, char, bool, references), a pass can instead hold the running maximum in a register and, at every comparison, write the smaller of it and the next element into the slot behind, with no branch on the outcome. The comparisons and their outcomes are the same; an element that is not overtaken is merely written back to its own slot.
• Two passes at once. Each branchless step waits for the one before it, so a single pass runs at the latency of a comparison. Pass k + 1 only reads slots that pass k has finished with, so it can trail pass k through the slice in the same loop: two independent chains of comparisons, each made exactly as if the passes ran one after the other; on random u64 input up to 1.3 times the speed of one branchless pass.

Branchless passes cost more than predictable branches, so the sort picks the kind of each pass from the previous one: a branchy pass that turns out to carry often gives way to branchless ones from where it stands, and branchless passes that move few elements hand back to branchy ones. Already sorted input is done by one branchy pass, as before. On random u64 and u32 input this sorts 1.2–2.9 times faster than branching on every comparison (most around a hundred elements), and input whose elements are each a few slots from their places up to 3.3 times faster.

The number of comparisons is exactly that of classic bubble sort with early exit, and so is every outcome; only the order in which two consecutive passes make them is interleaved. Zero-sized elements, which are all alike, are left as they are without comparing them.

Properties

• Stable: equal elements keep their relative order (only strictly smaller elements are overtaken).
• In place: O(1) auxiliary memory, no allocation.
• Adaptive: the cost grows with how far elements are from their sorted positions.

Case	Comparisons	Moves
Best (already sorted)	O(n)	0
Average	O(n²)	O(n²)
Worst (reverse sorted)	O(n²)	O(n²)

Bubble sort is quadratic and is mainly of educational value; 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: nothing is dropped twice or leaked.

Examples

use a::sort::bubble;

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

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