comparison sort lower bound

The proven fact that any sort that only compares pairs must make at least about n log n comparisons in the worst case.

In more detail

There are n factorial possible orderings of n items, and each comparison has two outcomes, so a decision tree that tells them all apart needs at least log2(n!) levels, which grows as n log n. This bounds every comparison sort, however clever. Only by using more than comparisons, such as integer digits, can a sort run in linear time.

Related terms

Taught in

References