Bubble vs Insertion vs Merge vs Quick Sort: 1,000 Bars Raced

0:00The Race: five sorts, one row of 1,000 bars

Here is a row of one thousand bars, shuffled. Each bar is a number. A taller bar is a bigger number. Sorting means putting them in order: shortest on the left, tallest on the right. Five sorting algorithms get this same shuffled row, on the same computer, and they start together. Bubble sort. Selection sort. Insertion sort. Merge sort. Quick sort. Every one of them works the same way. It iterates along the row, looking at bars and moving some of them. Then it goes back and does it again. Each trip along the row is called a pass. Next to each row is a counter. It counts how many passes that algorithm has made. Watch. Merge sort and quick sort are done almost at once, after only a few passes, and their counters stop. The other three have barely started, and their counters keep climbing, one pass at a time. Same bars, same computer, same job. So why does one algorithm finish so much sooner than another? It comes down to two things: how many passes an algorithm makes, and how far each pass goes. The fast ones make far fewer passes. So in this video, we count passes, not seconds. One chapter per algorithm, one idea each. After each chapter, the race runs again with that algorithm on the scoreboard. And in the last chapter: when your code calls sort, your computer runs none of these five exactly. It runs something built from two of them.

1:44Bubble + Selection: 999 passes, one bar each

Start with bubble sort, on just eight bars. Bubble sort looks at the first two bars. If the left bar is taller, it swaps them. Then it moves one step right and checks the next two bars, all the way to the end of the row. That trip is one pass. Watch the tallest bar. Every swap carries it along, until it reaches the last place, the way a bubble rises to the top. That's where the name comes from. After one pass, only one bar is sure to be in its final place: the tallest, at the right end. So bubble sort makes another pass, stopping one bar earlier, and the next tallest bar bubbles up beside it. With eight bars, bubble sort makes seven passes, each one bar shorter than the last. With one thousand bars, it makes nine hundred ninety-nine passes, and the early ones run almost the whole length of the row. Selection sort has the same goal, the tallest bar at the right end, but a different rule. On every pass, it looks through the whole unsorted part, selects the tallest bar, and moves it to the right end in one swap. Then it makes another pass, one bar shorter, and selects the next tallest. So selection sort also makes nine hundred ninety-nine passes on one thousand bars, every time. Both are slow for the same reason. The early passes cover nearly the whole row, and each one fixes only one bar. So one thousand bars need nine hundred ninety-nine long passes. Here's the race again, with two on the scoreboard. Bubble sort and selection sort both finish at nine hundred ninety-nine passes.

3:37Insertion: shorter passes and the almost-sorted row

Insertion sort works from the left. It keeps a sorted part at the left end of the row. At the start, that part is just the first bar, because one bar on its own is always in order. Insertion sort takes the next bar and compares it with the bar on its left. If the left bar is taller, the new bar slides past it, one step at a time. It keeps sliding left until it meets a shorter bar, and it stops there. Now the sorted part is one bar longer. It's the way you'd insert a new card into the cards already sorted in your hand. That's where the name comes from. Insertion sort repeats this for every bar, until the whole row is the sorted part. Each slide is one pass, so one thousand bars take nine hundred ninety-nine passes, the same as bubble sort. On a shuffled row, each pass slides the new bar, on average, about halfway into the sorted part. So insertion sort's passes are about half as long as bubble sort's. Here's the race with three on the scoreboard. All three counters end at nine hundred ninety-nine passes, but insertion sort's shorter passes finish first. Insertion sort beats the slow pair, but it's still far from fast. Now the trick. Give insertion sort a row that's already almost sorted, with only a few bars out of place. Each new bar is already taller than the bar on its left. Each pass is one step long, and the bar stays where it is. It still makes nine hundred ninety-nine passes, but each one is a single step. On that row, it beats every other algorithm in the race, even merge sort, whose few passes each run the whole row.

5:34Merge: ten passes, each the whole row

Merge sort starts from one easy fact: two rows that are already sorted are easy to join into one sorted row. Take two sorted rows of four bars. Merge sort compares the first bar of each row, and moves the shorter one into a new row. Then it compares the two first bars again. Each comparison places one bar. Joining two sorted rows this way is called a merge. That's where the name comes from. But a shuffled row has no sorted rows to join. So merge sort makes some. It cuts the row in half, then in half again, until every piece is a single bar. And one bar on its own is always sorted. Now merge sort merges back up. Single bars join into sorted pairs. Pairs join into sorted rows of four. And the two rows of four join into the sorted eight. On screen, that's three levels for eight bars. Each level is one pass: merge sort goes along the whole row once, and every bar gets placed once. One thousand bars need only ten levels, because halving one thousand ten times gets you down to single bars. So merge sort makes just ten passes, each one the whole row long. And that's the whole gap. Bubble sort needs nine hundred ninety-nine passes, because each pass fixes only one bar. Merge sort needs ten, because each pass doubles the length of every sorted row. Merge sort pays one price: it needs a second, empty row to build the merged rows in. Here's the race with four on the scoreboard. Merge sort finishes far ahead of the other three, after ten passes.

7:32Quick: the pivot and the sorted-row trap

Quick sort picks one bar from the row. That bar is called the pivot. It goes through the other bars once. Shorter bars go to the pivot's left. Taller bars go to its right. Now the pivot is in its final position. Everything on the left is shorter, and everything on the right is taller. The two sides are still shuffled, but the pivot never needs to move again. Quick sort repeats the same process on both sides: pick a pivot, split, and repeat, until every piece has just one bar. When the pivots land near the middle, each split roughly halves the remaining row. With one thousand bars, that's about ten levels, just like merge sort. Each level is one pass over the bars that are still unsorted. On shuffled bars, the pivots don't always land near the middle, so quick sort typically needs about twenty passes for one thousand bars. That's more than merge sort's ten, because the splits aren't perfectly balanced. But quick sort has an advantage. It rearranges bars in place, so it doesn't need a second row of storage. Now give it bars that are already sorted, and make it always pick the first bar as the pivot. The first bar is the smallest, so nothing goes left. Everything goes right. Each pass fixes just one bar. Quick sort now needs nine hundred ninety-nine passes, the same quadratic explosion you saw with bubble sort. Real implementations choose pivots more carefully, to reduce the chance of this happening. First, the race runs on shuffled bars. Merge sort and quick sort lead. Then the same race runs on bars that are already sorted. Insertion sort finishes first, and quick sort falls back with bubble and selection.

9:34What sort() Runs: Timsort in Python, Java and V8

Real lists are rarely shuffled. A list sorted yesterday gets a few new items added at the end. Prices arrive in time order. Real lists usually come with long stretches already in order. In two thousand two, Tim Peters wrote a sort for Python that looks for those stretches first. It's called Timsort, after him. Timsort makes one pass along the row and finds the stretches that are already in order. Each one is called a run. When a run is too short, Timsort makes it longer with insertion sort. That's the trick from chapter three: on a short stretch that's almost in order, each bar barely moves. Then Timsort merges the runs together, the same way merge sort joined sorted rows in chapter four. Each level of merging is one more pass. On a shuffled row, there are no long runs to find, so that first pass has to build every run with insertion sort. Timsort ends up doing about as much work as merge sort. On a row that's already sorted, Timsort's first pass finds a single run: the whole row. There's nothing to merge, so it stops after one pass. Python's sort is built on Timsort. Java uses it to sort objects. Chrome's JavaScript engine uses it to sort arrays. So here's the final race: all six, on a realistic row, mostly in order, with some new bars added at the end. Timsort finishes first. Its first pass finds the long run that's already in order, and only the new bars need real work. The fastest sort is the one that notices the work is already done.