Sorting algorithms

Notation in this table

• Θ(f) is a tight bound: the cost grows like f and no slower or faster. It is used wherever the bound is known to be tight.
• O(f) is an upper bound and Ω(f) is a lower bound. They are used where only one side is established.
• Best, average, and worst name the input, not the bound type. Quicksort, for example, is Θ(n log n) in the best and average cases and Θ(n²) in the worst case.
• Space is auxiliary space beyond the input array.

1. Quicksort space. O(log n) when the recursion handles the smaller partition first. A naive implementation can need O(n) stack space in the worst case.
2. Heapsort. The Θ(n log n) best case holds for distinct keys. Input where every key is equal can finish in O(n).
3. Bubble sort. The Θ(n) best case needs an early exit when a pass makes no swaps. Without it, every case is Θ(n²).
4. Tree sort. Assumes inserting into a plain binary search tree, which degrades to Θ(n²) on already-sorted input. A self-balancing tree makes the worst case Θ(n log n).
5. Shell sort. The running time depends on the gap sequence. Shell's original gaps give O(n²) in the worst case; sequences such as Pratt's give O(n (log n)²). Average-case bounds are not known for most sequences.
6. Bucket sort. The Θ(n+k) average assumes input spread roughly evenly across buckets. If most items land in one bucket, the cost is dominated by sorting that bucket, up to O(n²).

Topics on this page

Each one has its own page with an explanation, code, and the mistakes people make.

• Quicksort

  Θ(n log n) average; Θ(n²) worst case

• Mergesort

  Θ(n log n) in every case

• Heapsort

  Θ(n log n) for distinct keys

• Counting sort

  Θ(n + k) for values in a range of size k

• Python's built-in sort (Timsort)

  O(n log n) worst case; O(n) on already-sorted input