Sorting

Sorting is an important feature in user interfaces, but also provides the predictability that's necessary for many algorithms. Whenever there is no way to use an appropriate data structure (such as a tree), a generic sorting algorithm can take care of creating that order. One important question arises regarding equal values: will they end up at the same exact spot every time? When using a stable sorting algorithm, the answer is yes.

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