What is the lower bound for comparison-based sorting?

Options

1. O(n)
2. O(n log n) (Correct option)
3. O(log n)
4. O(n²)

Answer

O(n log n)

Why

A comparison sort only learns about the data by comparing two items ('is a < b?'). It can be proven that, in the worst case, any such algorithm needs about n log n comparisons.

So merge sort, heapsort and Timsort (O(n log n)) are already optimal.

Sorts that do not compare, like counting sort or radix sort, can be O(n) for limited kinds of keys (e.g. small integers).

Remember

Comparison sorting can't beat O(n log n).

Key terms

• Big-O notation
• Sorting algorithm
• Quicksort
• Heap / priority queue
• Time complexity
• Tree