Comparison-Based Sorting
Many sorting algorithms are comparison based.
They sort by making comparisons between pairs of objects
Sorting Lower Bound
Examples: bubble-sort, selection-sort, insertion-sort, heap-sort,
merge-sort, quick-sort, ...
Let us therefore derive a lower bound on the running
time of any algorithm that uses comparisons to sort n
elements, x1, x2, …, xn.
no
Is xi < xj?
yes
© 2004 Goodrich, Tamassia Sorting Lower Bound 1 © 2004 Goodrich, Tamassia Sorting Lower Bound 2
Counting Comparisons Decision Tree Height
Let us just count comparisons then. The height of the decision tree is a lower bound on the running time
Every input permutation must lead to a separate leaf output
Each possible run of the algorithm corresponds If not, some input …4…5… would have same output ordering as
to a root-to-leaf path in a decision tree …5…4…, which would be wrong
Since there are n!=1⋅2 ⋅ … ⋅n leaves, the height is at least log (n!)
xi < xj ?
minimum height (time)
xi < xj ?
xa < xb ? xc < xd ?
xa < xb ? xc < xd ?
log (n!)
xe < xf ? xk < xl ? xm < xo ? xp < xq ? xe < xf ? xk < xl ? xm < xo ? xp < xq ?
n!
© 2004 Goodrich, Tamassia Sorting Lower Bound 3 © 2004 Goodrich, Tamassia Sorting Lower Bound 4
The Lower Bound
Any comparison-based sorting algorithms takes at
least log (n!) time
Therefore, any such algorithm takes time at least
n
n 2
log (n!) ≥ log = (n / 2) log (n / 2).
2
That is, any comparison-based sorting algorithm must
run in Ω(n log n) time.
© 2004 Goodrich, Tamassia Sorting Lower Bound 5
