## Reading

These notes and
closely review

Unit 2
Section 3.

## Review quiz questions

We went over drawing the selection sort n=3 tree, and its
interesting features.

## Finishing off lower bounds

We finished off our proof that for any comparison-based sorting
algorithm, the worst case running time is $\Omega(n \lg n)$.

## Sorting review

We reviewed the sorting algorithms we know and their running
times: selection sort, insertion sort, merge sort, heap sort.
We also reviewed the limitations of our analysis, e.g. "is it
true that for any input array, merge sort is faster than
selection sort?". Why is the answer "no"?
## Reviewing sorting

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] \le; A[m+1] return

to the top of "merge". When the original input is already
sorted, this will make all the merge's 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)$.