A Better Lower Bound
The ?(n2) time bound does not apply to Quicksort, Mergesort, and Heapsort.
A better assumption is that keys can be moved an arbitrary distance.
However, we can still assume that the number of key-to-key comparisons is proportional to the run time of the algorithm.