Sorting
Arrange items in order. Comparison sorts cannot beat O(n log n); merge sort and quicksort get there by dividing the problem.
Level: intermediate
What is it?
Sorting rearranges a sequence into an order defined by a comparison. Simple sorts (bubble, insertion, selection) take O(n²). Merge sort splits the list, sorts each half, and merges in O(n log n); quicksort partitions around a pivot and averages O(n log n); heap sort uses a heap. Any comparison-based sort needs Ω(n log n) comparisons in the worst case. Stable sorts keep equal items in their original order.
Why does it matter?
Sorted data unlocks binary search, merging, grouping, deduplication, and range queries — and databases sort constantly for ORDER BY, joins, and index builds. Knowing the trade-offs (stability, memory, worst case) tells you which sort a library uses and why.
Mental model
Sorting a deck of cards by splitting the deck in half, sorting each pile separately (by splitting again), and then zipping the two sorted piles together, always taking the smaller of the two top cards. That zip is merge sort's merge.
How it works
- Insertion sort is O(n²) worst case but O(n) on nearly sorted data, so real sorts use it for tiny ranges.
- Merge sort: O(n log n) in every case, stable, needs O(n) extra space.
- Quicksort: O(n log n) on average, O(n²) worst case with bad pivots, in place, not stable.
- Heap sort: O(n log n) worst case, O(1) extra space, not stable.
- Counting and radix sort avoid comparisons and run in O(n + k) when keys are small integers.
- Python's sort() and Java's object sort use Timsort: a stable merge and insertion hybrid that exploits existing runs.
Steps
- Split into halves
- Sort each half recursively
- Compare the front of each half
- Take the smaller item
- Append the leftovers
Code example: Merge sort
def merge_sort(xs):
if len(xs) <= 1:
return xs
mid = len(xs) // 2
left, right = merge_sort(xs[:mid]), merge_sort(xs[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= keeps equal items in order (stable)
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]
print(merge_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9]Complexity and trade-offs
Time: O(n log n) for the good general-purpose sorts; Ω(n log n) lower bound for comparison sorts
Space: O(1) to O(n) depending on the algorithm
Trade-offs
- Merge sort is predictable and stable but uses extra memory
- Quicksort is fast in practice and in place but has a bad worst case and is not stable
- Non-comparison sorts beat n log n only when keys have a limited range
Real-world usage
- ORDER BY, merge joins, and index builds in databases
- Preparing data for binary search and deduplication
- External sorting for files larger than memory
Common mistakes
- Writing your own sort when the standard library's is faster and correct.
- Ignoring stability when sorting by several keys in passes.
- Choosing a pivot naively and hitting quicksort's O(n²) case on sorted input.
Interview questions
Why can't a comparison sort beat O(n log n)?
n items have n! possible orderings, and each comparison halves the possibilities at best, so at least log₂(n!) ≈ n log n comparisons are needed in the worst case.
What does it mean for a sort to be stable?
Items with equal keys keep their original relative order. It lets you sort by one key and then another and preserve the first ordering among ties.
Merge sort versus quicksort?
Merge sort guarantees O(n log n) and is stable, but uses O(n) extra space. Quicksort is usually faster in practice and sorts in place, but its worst case is O(n²) and it is not stable.
| Algorithm | Best | Average | Worst | Extra space | Stable |
|---|---|---|---|---|---|
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |