if A[m] ≤ A[m+1] returnto the top of "merge". When the original input is already sorted, this will make all the merges take constant time. This gave us a great opportunity to analyze a recursive algorithm. We also discussed that this hypothesis is impossible, because any correct sorting algorithm must at least examine every element in the array, so any sorting algorithm has a best case running time that is $\Omega(n)$. That's pretty cool, since we learned something about any algorithm anyone could ever devise.
$ T(n) \leq c n + T\left( \lceil n/2 \rceil \right) + T\left( \lfloor n/2 \rfloor \right) $We also showed how (with the help of Mathematica) to determine that this recurrence is $O(n \lg n)$.
Normally, our next step would be to analyze things to determine a lower-bound on the worst case running time. However, I decided we'd do something more ambitious, that is ...
One of the things that makes analyzing algorithms difficult, is that they are dynamic. An algorithm's state changes over the period of time in which it runs. However, it is possible with these sorting algorithms to talk about the algorithm as a static object, separated from any particular run of the algorithm. We saw how with an example. I showed in class how to construct the tree $T_3$ showing all possible ways insertion sort can run on a three element array.
One very interesting feature of this tree is that the worst-case running time for insertion-sort on three elements is given by the height of the tree. This will be important next class! Another important thing to note is the leaves. These represent the final order resulting from a run of insertion sort. You'll notice that all 3! permutations of x,y,z appear as leaves. This is in fact necessary, since there needs to be at least one path that gets you to each permuation, since any ordering is possible as input.
The key observation is that a sorting algorithm like insertion sort can be characterized by an infinite sequence of such trees: one for each input size.