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
- comparison sort — A sorting algorithm that learns about the order only by asking "is a smaller than b?" about pairs of items.
- decision tree — A tree in which each internal node is a question or choice and each path from the root to a leaf is one complete outcome.
- counting sort — A non-comparison sort for small non-negative integers that counts how many times each value occurs and then writes the values back out in order.
- big Omega notation — A way of writing a lower bound: Omega(f(n)) means the cost grows at least as fast as a constant times f(n) for large n.
Taught in
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- Counting And Radix Sort: Beating N Log N — Algorithms & Data Structures for Working Engineers