TimSort

Timsort is what actually sorts your lists in Python and Java. The idea behind it is simple: real data is hardly ever random. It almost always has stretches that are already in order, so timsort goes looking for those first and calls them runs. If it walks into a stretch heading the wrong way, downhill instead of up, it just flips it so that counts too. Short runs get padded out to a minimum length with a quick insertion sort, then the runs get merged back together in pairs, the same way merge sort does it.

This works best when the list is already mostly in order. Hand it a sorted list and the whole thing is one giant run, so it finishes in a single pass. That’s the O(n) best case. Hand it a fully reversed list and it finds one long run going the wrong way, flips it, and it’s done just as quick. Try the Sorted and Reversed inputs and watch the comparison count stay tiny, then hit Shuffle and watch it climb as the merging kicks in.

Hit Play to watch it run, or use Next and Back to step one move at a time. Shuffle deals a fresh array, the violet band is the run or pair it’s working on right now, and the highlighted line shows you where the code is at each step.