Let’s assume the left half of our input somehow miraculously gets sorted . . . And so does the right half . . . Can we use this to quickly reach a fully sorted list? Note that simply interleaving the two sequences doesn’t work. Instead, we’ll employ a more clever technique called merging. We compare the first two elements, and remove the darker one. We repeat this again . . . and again . . . until one side becomes empty . . . And then simply remove what remains. This process produces the elements in sorted order. Now, our robot will perform this merging algorithm. Being short sighted, it must bring the objects close to its eyes. When merging is done, the balls are pushed back to the bottom shelf and the sort is complete. Now let’s get back to a random permutation. To perform the merge algorithm, we need the two halves to be sorted. Instead of relying on miracles, we’ll sort each half ourselves. We’ll do it using … merge sort! We’ll split each half in half again, And again . . . Until we reach sequences of size one. These are already sort. And now we can work our way back up again . . . until we reach a fully sorted sequence. Two sequences of size one can be merged using a single comparison… Creating a sorted sequence of size two. Now that we have two of these, we can merge them into a sequence of size four. And so on… Both robots performed 19 comparisons, but quick sort did it more efficiently. Merge sort spent about 7 seconds moving elements from shelf to shelf. This approximately explains the time gap. But quick sort’s victory was partly due to luck: the first pivot it had randomly chosen split the row almost evenly. This is the optimal split. Its subsequent choices of pivots were lucky too. In the next round we’ll see what happens when quick sort is unlucky. Merge sort, on the other hand, makes no random choices. Its performance is only affected by the initial permutation. The last one turned out to be easy: In the final merge, for example, two balls remained on the left side, and there was no need to compare them with anything. Next, we’ll choose a permutation that will make merge sort work harder.
Over the last 5 years or so, single threaded CPU performance has barely budged while the number of cores has doubled every 2 years. With extremely parallel hardware on the horizon like Adapteva's parallella and IBM's SyNAPSE, we may reach a point where computational theory is turned on it's head. For example if you have more cores than data to sort everything becomes O(1). It's exciting to imagine what this post Von Neumann era could have in store for us.