Hands-On Data Structures and Algorithms with Rust

Unstable sorting

Unstable sorting does not retain the relative position of equal values, and can therefore achieve better speeds thanks to the lack of additionally allocated memory that stable sorting requires. The slice's sort_unstable() function uses a Quicksort variation that is called a pattern-defeating Quicksort by Orson Peters, combining heap sort and Quicksort to achieve an excellent performance in most cases.

The slice implementation simply refers to it as Quicksort:

    pub fn sort_unstable_by<F>(&mut self, mut compare: F)        where F: FnMut(&T, &T) -> Ordering    {        sort::quicksort(self, |a, b| compare(a, b) == Ordering::Less);    }

Looking at the Quicksort implementation, it spans the entire module—about 700 lines of code. Therefore, let's ...