Sorting Algorithms: Quicksort, Mergesort & Tradeoffs

Sorting Algorithms

Sorting — arranging data in order — is one of the most studied problems in computing, and for good reason: ordered data unlocks fast searching (binary search), deduplication, and countless algorithms that assume sorted input. Understanding how the major sorts work, and their tradeoffs, builds the intuition behind a huge amount of algorithmic thinking.

In practice you'll almost always call your language's built-in sort (a highly optimized O(n log n) hybrid). The value in knowing the algorithms is understanding why O(n log n) is the comparison-sort limit, what "stable" and "in-place" mean, and how to reason about the worst cases that occasionally bite.

TL;DR

Good general sorts are O(n log n): quicksort, mergesort, heapsort.
Simple sorts (bubble, insertion, selection) are O(n²) — fine only for tiny/nearly-sorted data.
Tradeoffs that matter: stability, in-place (memory), and worst case.
In real code, use the built-in sort — it's a tuned hybrid.

Quick Example

The built-in is what you reach for — with a key function for custom order:

The Major Algorithms

Real built-ins (Python's Timsort, Java's dual-pivot quicksort/Timsort) are hybrids that combine these — e.g. Timsort uses mergesort + insertion sort and exploits existing order.

How the Big Three Work

Quicksort — pick a pivot, partition elements into "less than" and "greater than," recurse on each side. Fast and in-place, but a poor pivot on already-sorted data degrades to O(n²) (mitigated by randomized/median-of-three pivots).
Mergesort — split the array in half, recursively sort each, then merge the sorted halves. Guaranteed O(n log n) and stable, but needs O(n) extra space. Great for linked lists and external sorting.
Heapsort — build a heap, then repeatedly extract the max. Guaranteed O(n log n) and in-place, though typically a bit slower in practice than quicksort due to cache behavior.

Stability & In-Place

Stable — equal elements keep their original relative order. This matters when sorting by multiple keys (sort by date, then stably by name). Mergesort and insertion sort are stable; quicksort and heapsort are not.
In-place — uses O(1) extra memory. Quicksort and heapsort are in-place; mergesort needs O(n) auxiliary space.

💡 The O(n log n) lower bound applies to comparison sorts. Specialized non-comparison sorts (counting sort, radix sort) can hit O(n) when keys are bounded integers.

Best Practices

Use the built-in sort — it's a tuned, stable hybrid; don't reimplement.
Provide a key function rather than sorting tuples by hand.
Rely on stability for multi-key sorts (sort by the least significant key first, or use a composite key).
Consider counting/radix sort when keys are bounded integers and you need O(n).
Don't sort to find one extreme — use a heap or a single pass for min/max/top-k.

Common Mistakes

Sorting just to find the top-k

Re-sorting inside a loop

FAQ

Which sorting algorithm should I actually use?

Your language's built-in sort, in almost every case. It's a carefully optimized O(n log n) hybrid (Timsort in Python/Java, introsort in C++) that handles edge cases, exploits partially-ordered data, and is stable where it matters. Reach for a specific algorithm only in special situations: counting/radix sort for bounded integer keys (O(n)), or a custom external merge sort for data too large to fit in memory. Learning the algorithms is for understanding, not reimplementation.

What does "stable" sorting mean and when does it matter?

A stable sort preserves the relative order of elements that compare equal. It matters whenever you sort by multiple criteria: sort a list of people by city, then stably by name, and people in the same city stay name-ordered. Without stability, the second sort would scramble the first. Mergesort and Timsort are stable; quicksort and heapsort are not. Most built-in sorts are stable, which is why multi-key sorting "just works."

Why is quicksort O(n²) in the worst case if it's usually fast?

Quicksort's speed depends on the pivot splitting the array into roughly equal halves. If the pivot is consistently the smallest or largest element (e.g. an already-sorted array with a naive first-element pivot), each partition removes only one element, giving n levels of O(n) work — O(n²). Randomized pivots or median-of-three selection make this worst case astronomically unlikely, which is why quicksort remains fast in practice despite the bad theoretical bound.

Can sorting be faster than O(n log n)?

For comparison-based sorts, no — O(n log n) is a proven lower bound, because distinguishing n! possible orderings requires at least that many comparisons. But non-comparison sorts can do better when you can exploit the structure of the keys: counting sort and radix sort achieve O(n) for integers in a bounded range by using the keys as indices rather than comparing them. They're not general-purpose, but they're powerful when their preconditions hold.