Sorting Complexities and the Lower Bound

How fast can sorting be?

Simple sorts such as bubble, selection and insertion sort take O(n²) time in the worst case; insertion sort is O(n) on nearly sorted input, which is why hybrid algorithms use it for small pieces. Merge sort is Θ(n log n) in all cases and stable, but needs O(n) extra space. Quicksort is O(n log n) on average and usually fastest in practice, but O(n²) in the worst case with bad pivots (randomised or median-of-three pivots make this unlikely). Heapsort is O(n log n) worst case and in-place, but not stable. Real libraries use hybrids: Timsort (Python, Java for objects) and introsort or pdqsort variants (C++). A fundamental result: any comparison-based sort needs Ω(n log n) comparisons in the worst case, because there are n! possible orderings and each comparison has two outcomes, so a decision tree needs height at least log₂(n!) = Θ(n log n). Non-comparison sorts beat this bound for special data: counting sort is O(n + k) for integers in a range of size k, and radix sort is O(d·(n + k)) for d-digit keys.

Sorting algorithms compared

Time and auxiliary space; stable means equal keys keep their order.

algorithm        best        average     worst       extra space   stable
---------------  ----------  ----------  ----------  ------------  ------
bubble sort      O(n)        O(n^2)      O(n^2)      O(1)          yes
selection sort   O(n^2)      O(n^2)      O(n^2)      O(1)          no
insertion sort   O(n)        O(n^2)      O(n^2)      O(1)          yes
merge sort       O(n log n)  O(n log n)  O(n log n)  O(n)          yes
quicksort        O(n log n)  O(n log n)  O(n^2)      O(log n) avg  no
heapsort         O(n log n)  O(n log n)  O(n log n)  O(1)          no
counting sort    O(n + k)    O(n + k)    O(n + k)    O(n + k)      yes
Timsort          O(n)        O(n log n)  O(n log n)  O(n)          yes

Twenty questions for orderings

Sorting by comparisons is like playing twenty questions where each yes/no question narrows down which of the n! possible orders you have. You cannot guarantee finding the answer with fewer than log₂(n!) questions.

त्वरित जाँच: Why can counting sort run faster than Ω(n log n)?

• It uses better comparisons
• It only works on sorted input
• It ignores half the elements
• It is not comparison-based; it uses the integer values directly within a known range