This video is on lower bounds for comparison based sorting using decision trees. You should have already seen some of these basic sorting algorithms, I specifically use insertion sort the most here. After some motivation, I use it to explain what a comparison based sort is, and specifically look at how it acts on three elements.
We will introduce decision trees, and how they relate back to the algorithm, and show trees for each of those previously listed sorts. We use those trees to make a lower bound argument for sorting three items, and then generalize that to prove a lower bound for sorting n items. Let's say the first sorting algorithm you learned is insertion sort, and afterwards you're like, great, now I know how to sort, it's got to be useful. So you slap it into your LinkedIn and Tinder profiles, but no job offers. Then you learn merge sort, and you realize that insertion sort isn't that great.
Insertion sort's n-squared doesn't look so good once you know that you can do better, and sort in n log n. But is n log n good? Well, can you do better? Here's the insertion sort algorithm. Let's consider running that algorithm on an array with just three items.
If that code is running, the outcomes of the comparisons between the elements from A tell us everything there is to know about what is happening in the code. So if the first comparison comes out true, the first two items of the array will get swapped, otherwise they won't. Either way, I won't enter that while loop a second time until we're in the second pass of the outer for loop. An ordered list of true-false outcomes for the comparisons tells us everything that there is to know about what happens in the code, even without a list of what was compared. The first comparison is between the first two elements, the second comparison is between the third element, and whichever of the first two elements is smaller, assuming they are different.
If that second comparison comes out false, there isn't a third comparison. If the first two comparisons are false, the numbers were given to you in increasing order. This is what we are talking about when we say a comparison-based sorting algorithm. The important data-driven forks in the code happen because two different elements are compared against each other, and the outcome of that comparison determines what will happen next in the code. Insertion, bubble, selection, heap, merge, and quicksorts are all comparison-based sorting algorithms, and there are more.
There are general sorting algorithms that can sort any inputs as long as input values can be comp- paired to each other, with just three items, we know that we go through that outer loop twice. Let's get rid of the loop. For the comparisons inside the while loop, what happens depends on the outcome of those comparisons.
I'm going to get rid of those loops too, while keeping the same comparisons between the same elements in the same order, but the rest of the code looks different. This code is ugly. But, you could write it once you know if-else statements without knowing loops. It has the original comparisons, and they will be executed in the same order as the original code, starting with the first two items. But all comparisons are now written explicitly.
If we consider running insertion sort on the numbers, we can see the three comparisons the code will perform. Like any comparative based sort, it's the relative sizes of the inputs that are important, not the absolute values. So insertion sort will go through the same steps to sort 11, 13, 12, as it does for 1, 3, 2. The problem here is that this is just a horrific way to see what's happening, so let's introduce decision trees.
Here is a decision tree. for insertion sort on three items. It might look like some kind of data structure, but it isn't.
It's just a more visual representation of which elements get compared by the code. The non-leaf nodes of the decision tree represent the comparisons, and the two children for a node represent the two possible outcomes of its comparison. The leaves represent final outcomes for the program.
So we can again look at what happens on input 132 and see which leaf we get to. That path, from the decision tree root to a leaf, represents running the algorithm on some particular set of data. Each inner node on the path represents a comparison that the algorithm does in that order. The length of the path is the number of comparisons the algorithm does for that input. It's easy to see here that while 1, 3, 2 has three comparisons, Other inputs, like 2, 1, 3, have only 2. Different sorting algorithms have different decision trees.
If we look at bubble sorts tree, we see that it always performs 3 comparisons, although for 2 possible inputs, the last comparison doesn't tell you anything you didn't already know. The Korman book only broadly defines selection sort in an exercise, but for my implementation? That also happens for one input to selection sort.
You also get this weird seventh outcome, where if the first two elements are equal, but larger than the third, it sorts, but unstably puts the second item before the first. Weird stuff isn't exclusive to quadratic sorts. Heapsort has two of those useless comparisons, a bunch of unstable outputs, and this strange leaf node that you hit.
If the first value is strictly less than the second, and the third is somewhere between those two, but if all three are equal, you go to a completely different node. You wouldn't choose to make redundant comparisons if you were making a tree for three items from scratch, but to write code that cleanly works on any number of inputs using natural operations on a heap, some comparisons can be duplicated. This is the decision tree. for both top-down and bottom-up merge sort.
Those are different algorithms, with different trees for 5 or more elements, but for 4 or less, they have the same trees. Meanwhile, for just 2 items, if you are only doing one comparison, there are pretty much only 2 possible trees, depending on if you are stable on 2 equal items or not. Finally, the tree for quicksort, we can see its instability.
in this output. So some of these trees always take three comparisons, while others sometimes use two, and other times use three. The real question is, can we make a tree with at most two comparisons? Well, no. Each of these trees has at least six leaf nodes, because if I give the program three distinct values, like one, two, three, There are 6 possible permutations that you can order the input.
Each comparison has at most 2 children, for the possible outcomes of the comparison. If I try to make a binary tree with at most 2 comparisons, it gives me a tree with height at most 2, with at most 4 leaves. To get 6 permutations into 4 leaves, at least 2 permutations must go to 1 leaf, and the algorithm will do the exact same thing for both of those permutations. If you reorder two different permutations in the same way, like keep the first element first, but swap the other two, at most one of those two permutations can be sorted afterwards.
So every permutation needs to get its own leaf. It boils down to the problem that 6 is not less than or equal to 4. So no matter what your comparison-based sorting algorithm is, for three items, it's decision tree. It needs height at least 3, and some inputs will require 3 comparisons.
Finally, to the finale, we don't want to sort just 3 items, we want to sort n items. Great. Assume that you have some comparison-based sorting algorithm for sorting n items. Instead of just 6 permutations, n items can come in n factorial permutations.
So, the decision tree for the algorithm will have to have at least n factorial leaves. If the decision tree's height is h, it will have at most 2 to the h leaves. So, 2 to the h has to be at least n factorial, and h has to be at least order n log n. If the tree has height order n log n, that means that, in the worst case, the decision tree makes order n log n comparisons, so the algorithm takes at least n log n time.
That is, no matter how clever. Any comparison-based sorting algorithm will take at least n log n runtime in the worst case. That's it. That's the whole argument.
It doesn't prove that n log n comparisons are sufficient, it just proves it as a lower bound. Of course we know that order n log n comparisons are sufficient, because merge sort and heap sort both follow that bound, so you won't find it. a general sorting algorithm asymptotically faster than them.
Besides comparison-based sorts, the playlist does have some non-comparison-based sorts in the linear sorts video, but for now, time to go update those profiles. Good luck.