Algorithms
Sorting Algorithms
Sorting algorithms rearrange a collection of items into order. The right choice depends on input size, value range, memory constraints, and whether ties must keep their original order. Here's a practical guide — the comparison table first, then each algorithm in depth.
At a glance
Every sorting algorithm trades the same three resources differently — time, memory, and the stability of equal-valued items. The best one for your situation depends on what you have plenty of and what's scarce.
Use the comparison table below to pick a candidate, then click into each algorithm for a step-by-step interactive visualization and a 60-second video explainer.
| Algorithms | Time (avg) | Time (worst) | Space | Stable | In-place | Best for |
|---|---|---|---|---|---|---|
| Merge Sort | O(n log n) | O(n log n) | O(n) | Yes | No | Linked lists, external sorts, predictable performance |
| Quick Sort | O(n log n) | O(n²) | O(log n) | No | Yes | General-purpose in-memory sorting; cache-friendly |
| Bubble Sort | O(n²) | O(n²) | O(1) | Yes | Yes | Teaching, near-sorted small inputs |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | Yes | No | Bounded integer keys (ages, grades, byte values) |
Each algorithm in depth
Click any card for the full article with an interactive visualization, complexity analysis, code examples, and FAQ.
-
Merge Sort
Divide-and-conquer: recursively split the array in half, sort each half, then merge. Guaranteed O(n log n), stable, but uses O(n) extra memory.
View interactive ↗ -
Quick Sort
Pick a pivot, partition the array so smaller items go left and larger right, recurse on each side. Usually the fastest in practice — but a bad pivot choice degrades to O(n²).
View interactive ↗ -
Bubble Sort
Walk through the array swapping adjacent pairs that are out of order. Each pass bubbles the next-largest element to its place. Easy to understand, terrible at scale.
View interactive ↗ -
Counting Sort
A non-comparison sort that runs in O(n + k) when values come from a small integer range. Counts occurrences in a bucket array, then writes them back in order.
View interactive ↗
Which one should you reach for first?
For general-purpose in-memory sorting, quick sort (or a hybrid like Timsort, used by Python and Java) wins on average — it's cache-friendly and the constant factors are tiny. Standard libraries default to it for a reason.
For predictable worst-case performance — say, a real-time system that can't tolerate a O(n²) pathological case — use merge sort. The 2× memory overhead is worth the guarantee.
For bounded-integer data (ages, grades, byte values, DNA bases), nothing beats counting sort's O(n + k) — it's literally faster than the O(n log n) lower bound for comparison sorts because it doesn't compare.
Use bubble sort only as a teaching tool, or when you're certain the input is tiny (under 30 elements) and already nearly sorted.
Stability matters more than you think
A stable sort preserves the original order of equal-valued items. That sounds academic until you sort a table of (name, score) pairs by score and find that names within the same score get scrambled. With a stable sort, you can sort by score, then by date, then by name, and end up with rows ordered by score primarily, name secondarily — without any tie-breaking logic.
Of the algorithms above, merge sort, bubble sort, and counting sort are stable. Quick sort as typically implemented is not — though stable variants exist with extra memory.
The Ω(n log n) lower bound
Any algorithm that sorts by comparing pairs of elements needs at least Ω(n log n) comparisons in the worst case — this is provable from a decision-tree argument. That's why merge sort and quick sort feel like the floor for general-purpose sorting.
Counting sort, radix sort, and bucket sort sidestep the bound by not comparing — they exploit structure in the keys. That's why they can be faster than O(n log n) on inputs that fit their model.
Frequently asked questions
Which sorting algorithm is fastest in practice?
For most general-purpose workloads, hybrid algorithms like Timsort (Python, Java's Arrays.sort for objects) or pdqsort (Rust) are fastest. They blend quick sort, merge sort, and insertion sort to capture each algorithm's strengths and avoid their weaknesses.
Is quicksort always faster than merge sort?
On average, yes — quick sort has smaller constant factors and is cache-friendly. But its worst case is O(n²) when pivots are pathological. Merge sort guarantees O(n log n) but uses O(n) extra memory and has worse cache behavior.
When would I choose bubble sort?
Almost never in production. Bubble sort is useful as a teaching tool to introduce the concept of comparison-based sorting, and its constant-factor simplicity occasionally wins on tiny (n < 16) nearly-sorted inputs — though insertion sort is usually a better choice even there.
Why isn't counting sort the universal default?
Counting sort runs in O(n + k) where k is the range of values. When k is huge — for example, sorting 64-bit integers or arbitrary strings — the bucket array dominates and the algorithm becomes impractical. It only beats comparison sorts when the value range is bounded and small relative to n.
What's the difference between stable and unstable sorts?
A stable sort preserves the relative order of items that compare equal. If you sort records by date and then by name, a stable sort keeps the date-ordering within each name group. An unstable sort may scramble it. Merge sort, bubble sort, and counting sort are stable; quicksort typically isn't.
Can sorting be faster than O(n log n)?
For comparison-based sorts, no — there's a provable Ω(n log n) lower bound. But non-comparison sorts (counting, radix, bucket) can be O(n) on inputs whose keys have exploitable structure (bounded integer range, fixed-width digits, uniform distribution).