Sorting
Order a list — ten ways. From the textbook swap-adjacent sorts you write in a single loop, to the divide-and-conquer giants, to the non-comparison tricks that beat O(n log n), to the hybrid your language's sort() actually uses.
What is Sorting?
The 60-second primer
Sorting is the first algorithm topic every programmer learns, and the only one you'll keep meeting forever. Databases pre-sort to make joins cheap. Search engines pre-sort to do binary search. Log pipelines sort by time. The hash-and-route layer in front of every API sorts buckets internally. Every programming language ships a sort() — and inside that one function is roughly fifty years of engineering you should know about.
The ten algorithms here split into three families. Comparison sorts ask a < b? and shuffle elements around — bubble, selection, insertion, merge, quick, heap. Theory says these can't beat O(n log n) in the worst case. Non-comparison sorts sidestep that bound by looking at the values themselves — counting, radix, bucket — and run in O(n + k) when the data fits their assumptions. Hybrid sorts — Timsort — combine the best of comparison sorts with awareness of real-world data, which is rarely random.
Don't think of them as ten interchangeable boxes. Each one was the right answer to a specific situation: bubble teaches the swap; insertion is the right tool for nearly-sorted lists; quicksort wins the in-memory race when you control the pivot; mergesort is the right tool for stable external sorts; heapsort is the safe choice when you cannot tolerate quicksort's worst case; counting/radix/bucket all win when your data is integers in a known range; Timsort wins on the messy, partially-sorted lists that show up everywhere in practice.
Where this shows up
- Your language's sort() — Python, Java, Rust, JavaScript V8 all ship Timsort or a close relative. Go and C++ use intro-sort, a quicksort that falls back to heapsort on bad pivots.
- Databases —
ORDER BYruns an external mergesort when the data doesn't fit in RAM; B-tree pages stay sorted on disk so range scans are cheap. - Indexing pipelines — Lucene, Elasticsearch, BigQuery, Spark all sort intermediate results to enable merge-joins and grouped aggregations.
- Networking — packet schedulers sort by deadline; routers sort by prefix length; Kademlia and other DHTs sort peers by XOR-distance.
- Graphics & games — depth-sorted transparency, BVH construction, A* open-set priority queues all hide a heap or a radix-style sort inside.
- Coding interviews & data structures — most algorithms problems either are a sort or use one as a preprocessing step. Sorting is the universal primitive.
Why so many algorithms still matter
It's tempting to memorise 'just use quicksort.' But quicksort hates already-sorted input. Mergesort needs O(n) extra memory. Counting sort needs a known small key range. Bucket sort needs roughly uniform data. Insertion sort beats everything on lists under ~16 elements. Real sort() implementations stitch several of these together — Timsort uses insertion for small runs and merge for everything else; Java's Arrays.sort uses dual-pivot quicksort for primitives and Timsort for objects. The reason there's no one winner is the algorithms aren't competing on the same problem.
Side-by-side
How they compare
The same concepts, on the same axes. Use this as a map; the individual pages are the territory.
| Algorithm | Best | Average | Worst | Best for |
|---|---|---|---|---|
01Bubble Sort | O(n) | O(n²) | O(n²) | Teaching the swap primitive. Don't use it in real code. |
02Selection Sort | O(n²) | O(n²) | O(n²) | When writes are far more expensive than reads (e.g. flash memory). |
03Insertion Sort | O(n) | O(n²) | O(n²) | Small lists (n < ~16) and nearly-sorted data. The inner loop of Timsort. |
04Merge Sort | O(n log n) | O(n log n) | O(n log n) | Stable sorting; external sorts that don't fit in RAM; linked lists. |
05Quick Sort | O(n log n) | O(n log n) | O(n²) | In-place, cache-friendly sorting when you control the pivot. |
06Heap Sort | O(n log n) | O(n log n) | O(n log n) | Hard worst-case guarantees; embedded systems with no recursion budget. |
07Counting Sort | O(n + k) | O(n + k) | O(n + k) | Integer keys in a small known range — frequency tables, vote counts. |
08Radix Sort | O(d · (n + k)) | O(d · (n + k)) | O(d · (n + k)) | Fixed-width integer keys at scale — IP addresses, timestamps, hashes. |
09Bucket Sort | O(n + k) | O(n + k) | O(n²) | Roughly uniform floats — `sort(random_array)` is its dream input. |
10Timsort | O(n) | O(n log n) | O(n log n) | Real-world data with existing partial order. The default in Python/Java/JS. |
- Best
- O(n)
- Average
- O(n²)
- Worst
O(n²)- Best for
- Teaching the swap primitive. Don't use it in real code.
- Best
- O(n²)
- Average
- O(n²)
- Worst
O(n²)- Best for
- When writes are far more expensive than reads (e.g. flash memory).
- Best
- O(n)
- Average
- O(n²)
- Worst
O(n²)- Best for
- Small lists (n < ~16) and nearly-sorted data. The inner loop of Timsort.
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
O(n log n)- Best for
- Stable sorting; external sorts that don't fit in RAM; linked lists.
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
O(n²)- Best for
- In-place, cache-friendly sorting when you control the pivot.
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
O(n log n)- Best for
- Hard worst-case guarantees; embedded systems with no recursion budget.
- Best
- O(n + k)
- Average
- O(n + k)
- Worst
O(n + k)- Best for
- Integer keys in a small known range — frequency tables, vote counts.
- Best
- O(d · (n + k))
- Average
- O(d · (n + k))
- Worst
O(d · (n + k))- Best for
- Fixed-width integer keys at scale — IP addresses, timestamps, hashes.
- Best
- O(n + k)
- Average
- O(n + k)
- Worst
O(n²)- Best for
- Roughly uniform floats — `sort(random_array)` is its dream input.
- Best
- O(n)
- Average
- O(n log n)
- Worst
O(n log n)- Best for
- Real-world data with existing partial order. The default in Python/Java/JS.
Decision guide
Which one should you use?
A practical tour of when each algorithm wins.
How to pick
- You just need it sorted → call your language's built-in
sort(). It's Timsort or intro-sort; both are near-optimal for general data and have been hardened by millions of users. Don't reinvent. - Your data is integers in a known range (votes 0-9, ages 0-120, byte values 0-255) → counting sort. It's linear and easier to write than you'd think.
- Your data is fixed-width integers at huge scale (IPv4 addresses, 64-bit hashes) → radix sort. Beats comparison sorts at billion-element scale.
- *You need a stable sort and have memory to spare → merge sort* (or Timsort, which is also stable). Stability matters when ordering by multiple keys: sort by name then by date, the dates within each name stay in original order.
- You need worst-case O(n log n) guarantees (real-time systems, hostile inputs) → heap sort or intro-sort (quicksort + heapsort fallback). Pure quicksort is fast on average but can be tricked.
- Your list is small (n < ~16) or nearly sorted → insertion sort. That's why it's inside Timsort and inside std::sort's small-array base case.
- You're teaching → start with bubble for the swap, insertion for the real-world card-sorting analogy, then merge to introduce divide-and-conquer.
Stable vs unstable sorts
A stable sort keeps equal elements in their original order. Merge sort, insertion sort, bubble sort, counting sort, radix sort, and Timsort are stable. Selection sort, quick sort, and heap sort are not. Stability matters more than it sounds: it's what lets you sort by multiple columns by sorting once per column, in reverse priority order.
Concepts in this track
10 concepts, in order
Each links to a concept page with its own explanation, prototype, and quiz.
Bubble Sort
Sweep through the list swapping any out-of-order neighbours. The biggest value bubbles to the end each pass.
Selection Sort
Each round, find the smallest remaining value and swap it into the next sorted slot. One swap per pass — minimum movement.
Insertion Sort
Pick up each value and slide it into its place in the sorted left side — exactly how you sort cards in your hand.
Merge Sort
Split until each piece is one element, then merge sorted pairs back together. The classic O(n log n) divide-and-conquer.
Quick Sort
Pick a pivot, partition the rest into smaller-than and larger-than, then recurse on each side. Fast in-place — and famously fragile on adversarial inputs.
Heap Sort
Pour the array into a max-heap, then repeatedly pull the largest off the top. O(n log n) worst-case, in-place, no recursion.
Counting Sort
Tally each value, prefix-sum the tallies into end positions, then place every item directly. O(n + k) — no comparisons at all.
Radix Sort
Sort by one digit at a time — ones, then tens, then hundreds — using a stable bucket pass per digit.
Bucket Sort
Scatter values into range buckets, sort each bucket on its own, then concatenate. Near-linear when the inputs are roughly uniform.
Timsort
Find runs already in order, pad short ones with insertion sort, then merge runs in stack order. The hybrid your language's sort() actually ships.
Related tracks
If this one clicks, try these next.
Graph Algorithms
How computers reason about networks of things — roads, friends, packets, dependencies. Ten algorithms, from the two traversals every other algorithm is built on, to weighted shortest paths, minimum spanning trees, and the heuristic search behind every modern pathfinder.
Rate Limiting
Control request throughput so a noisy client cannot starve everyone else. Compare the five canonical algorithms side-by-side.
Cache Write Policies
Three ways to handle a write when you have a cache in front of the store. Each policy is a different bet about durability, throughput, and how stale your data is allowed to get.