Pull up a chair. You have probably seen a table of sorting algorithms with columns of Big-O entries, and maybe you memorised it. Let us make some sense of it instead, because once you see where those numbers come from, you will not need to memorise them.
The slow way first
Bubble sort, insertion sort and selection sort all do roughly the same thing: for each element, scan through many of the others. With 1,000 items that is on the order of n × n / 2, about 500,000 comparisons. For 100,000 items it is about five billion. That is the n² family, and it is why nobody sorts a large list this way.
Insertion sort deserves one kind word, though. If the list is already nearly sorted, it barely does any work, because each new element only needs to move a short distance. Hold on to that; it comes back later.
Divide, then combine
Merge sort works like this. Split the list in half. Sort each half, by the same method. Then merge the two sorted halves, which is cheap: you keep a finger on the front of each half and repeatedly take the smaller front item. Merging n items costs about n steps.
How many times can you halve 1,000 items before you reach single items? About ten, since 2 to the power 10 is 1,024. So there are around ten levels, and each level does about n work in total for merging. Ten levels times 1,000 is roughly 10,000 steps, against 500,000 for the slow way. In symbols, that is n log n. The cost of halving is the log n; the cost of merging at each level is the n.
The price of merge sort is memory: it normally needs a spare array about the size of the input to merge into. On the plus side, it is stable, meaning that items with equal keys keep their original relative order. If you sort employees by department and then by joining date, stability is what stops the second sort from scrambling the first.
Quicksort: the gambler
Quicksort picks one item, the pivot, and rearranges the list so everything smaller sits to its left and everything larger to its right. Then it sorts each side the same way. If the pivot lands near the middle each time, you get the same halving as merge sort, with n log n total. It works in place, with little extra memory, and has good cache behaviour, which is why it is fast in practice.
The catch is a bad pivot. If you always pick the first element and the list is already sorted, the pivot is always the smallest item, one side is empty, and you have n levels of work instead of log n. That is n² behaviour on the very input that looks easiest. Real implementations reduce the risk with random pivots, median-of-three choices, or by switching to a different algorithm when recursion gets too deep (a hybrid known as introsort). Basic quicksort is also not stable.
Why n log n is a floor
Here is a nice argument. Suppose the only thing you may do is compare two items. A list of 1,000 distinct items can be arranged in 1,000 factorial different orders, and your algorithm must work out which one it was. Each comparison gives a yes or no answer, so it can at best halve the remaining possibilities. To distinguish between 1,000! possibilities you need at least log base 2 of 1,000! comparisons, which works out to about 8,530. That is close to 1,000 × log2(1,000), which is about 9,966, and the gap shrinks proportionally as n grows. So no comparison-based method can beat n log n in the worst case. It is not that nobody has been clever enough; it is a limit.
The limit has a loophole: it only applies when you sort by comparing. Counting sort and radix sort, for example, can sort integers in a limited range in time proportional to n, because they use the values as positions and never compare. They need extra assumptions, such as small known key ranges.
What your language actually calls
Python’s built-in sorted and list.sort use Timsort, designed by Tim Peters. It is a merge-sort hybrid that looks for already-ordered runs in the data and merges them, using insertion sort for short stretches. On nearly sorted data it approaches linear time, and it is stable. Java uses Timsort too for sorting objects, and a dual-pivot quicksort for primitive arrays such as int[], where stability does not matter since equal numbers are indistinguishable. JavaScript’s Array.prototype.sort has been required to be stable since ES2019. Details vary by language version and runtime, so check the documentation of what you use if it matters.
What to take back to your desk
Use the library sort; you will rarely beat it. Choose it with stability in mind when you sort by multiple keys. Remember that a sort on a comparator costs n log n comparisons, so an expensive comparator, like one that parses dates on every call, hurts you twice over: prepare the keys once, then sort. And when someone asks which algorithm is “best”, the honest answer is a question back: how big, how ordered, how much memory, does stability matter? That is how you would decide in real work too.
Figures and names in the examples are illustrative.
Leave a Reply