The Complete Rust Programming Reference Guide

Quicksort

This algorithm significantly outperformed merge sort in best case scenarios and was quickly adopted as Unix's default sorting algorithm, as well as in Java's reference implementation. By using a similar strategy to merge sort, Quicksort achieves faster average and best case speeds. Unfortunately, the worst case complexity is just as bad as bubble sort: O(n²). How so? you might ask.

Quicksort operates, sometimes recursively, on parts of the full collection, and swaps elements around to establish an order. Hence, the critical question becomes: how do we choose these parts? This choosing bit is called the partitioning scheme and typically includes the swapping as well, not just choosing a split index. The choice is made by picking ...