Unstable sorting

There is also an interesting place where some gains can be made. Usually, when you want to sort a vector, for example, stable sorting is used. This means that if two elements have the same ordering, the original ordering will be preserved. Let's see it with an example. Suppose we have a list of fruits we want to order alphabetically, taking into account only their first letter:

    let mut fruits = vec![
        "Orange", "Pome", "Peach", "Banana", "Kiwi", "Pear"
    ];
    fruits.sort_by(|a, b| a.chars().next().cmp(&b.chars().next()));

    println!("{:?}", fruits);

This will print exactly the following:

And in that order. Even though Peach and Pear should be before Pome if we did the sorting by the whole word, since we only take the first character into account, the ordering is correct. The final order depends on the one at the beginning. If I changed the first list and put Pome after Peach, the final order would have Pome after Peach. This is called stable ordering.

On the other hand, unstable ordering doesn't try to preserve previous ordering. So, Pome, Peach, and Pear could end up in any order between them. This is consistent with the condition of being ordered by the first letter, but without preserving the original order.

This unstable sorting is actually faster than the stable sorting, and if you don't care about respecting the initial ordering, you can save valuable time doing the sorting operation, one of the most time-consuming operations. A simple example is ordering a list of results alphabetically. In the case of a mismatch, you usually don't care how they were ordered in the database, so it doesn't matter if one comes after the other or the other way around.

To use unstable sorting, you will need to call sort_unstable() or sort_unstable_by(), depending on whether you want to use the default comparison of each PartialOrd element or use your own classifier, if you want a custom one or if the elements in the vector are not PartialOrd. Consider the following example using unstable sorting:

    let mut fruits = vec![
        "Orange", "Pome", "Peach", "Banana", "Kiwi", "Pear"
    ];
    fruits.sort_unstable_by(|a, b| a.chars().next().cmp(&b.chars().next()));

    println!("{:?}", fruits);

A possible output for this would be the following, impossible with stable sorting:

So, summarizing, if you really need to maintain the ordering of the input, use stable sorting; if not, use unstable sorting, since you will make your program much faster.