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.
lSorting methods that achieve this lower bound are called ÒoptimalÓ.
lHeapsort and mergesort are the two optimal sorts weÕve studied.