These notes and
closely review Unit 2
Review quiz questions
We went over drawing the selection sort n=3 tree, and its
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)$.
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"?
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)$.