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