Hands-On Data Structures and Algorithms with Rust

Stable sorting

The key to stable sorting is not reordering equal elements, so in [1, 1, 2, 3, 4, 5], 1s never change their positions relative to each other. In Rust, this is actually used when sort() is called on Vec<T>.

The current (2018 edition) implementation of Vec<T> uses a merge sort variation based on Timsort. Here is the source code:

pub fn sort(&mut self)    where T: Ord{    merge_sort(self, |a, b| a.lt(b));}

The code is quite verbose, but can be split into smaller parts. The first step is to sort smaller (20 elements or less) slices by deleting and reinserting the elements in order (in other words, insertion sort):

fn merge_sort<T, F>(v: &mut [T], mut is_less: F)    where F: FnMut(&T, &T) -> bool{ // Slices of up to this length get sorted ...