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 ...

Get Hands-On Data Structures and Algorithms with Rust now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.