[prev] 71 [next]

Sorting Lower Bound for Comparison-Based Sorting

Many popular sorting algorithms "compare" pairs of keys (objects) to sort an input sequence.

For example: selection-sort, insertion-sort, bubble-sort, merge-sort, quick-sort, etc.

Lower Bound: Any comparison-based sorting algorithm must take Ω (n log n) time to sort n elements in the worst case.