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|;}

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 the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.