These notes and closely review Unit 2 Section 2 and Section 3.



Another merge improvement

Midn X suggested an improvement to mergesort that he hypothesized would make its best case $\Theta(\lg n)$. The improvement is to add
if A[m] ≤ A[m+1] return
to 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.

Analyzing MergeSort — a review

Recall that in the previous class we decided that the worst-case time for mergesort is given by the following recurrence relation:

$ 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 ...

Prove that any comparison-based sorting algorithm has $T_w(n) \in \Omega(n \lg n)$

By "prove that any comparison-based sorting algorithm has $T_w(n) \in \Omega(n \lg n)$", I mean that any algorithm, including any super-clever advanced algorithm produced by future generations. That's pretty ambitious, no? How can I prove what future generations can't do?

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.

Tree for Gnomesort

We looked at the tree for Gnomesort and $n=3$, and saw the indications that Gnomesort isn't a very good sorting algorithm: the tree height was large (meaning bad worst-case number of comparisons) and it had lots of comparison nodes without branches (meaning redundant comparisons).