# Sorting Complexities and the Lower Bound — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/a-sorting

> Compare sorting algorithms and explain the Ω(n log n) comparison 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.

```text
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.

**Quiz:** 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
- [x] It is not comparison-based; it uses the integer values directly within a known range

*Answer:* It is not comparison-based; it uses the integer values directly within a known range. The lower bound applies only to comparison sorts; counting sort indexes by key value.