Lower-Bound for Sorting
lSorting based on pairwise comparisons (which excludes radix and bucket sorts) requires a minimum of c n log2(n)
steps.
lSorting methods that achieve this lower bound are called ÒoptimalÓ.
lHeapsort and mergesort are the two optimal sorts weÕve studied.