Sorting Algorithms Roadmap
Every classic sorting algorithm, from bubble sort to Timsort: 17 topics in four stages, each with what to learn, free resources, something to build and a set of easy, medium and hard LeetCode problems, 61 in all. Every algorithm topic links to our sorting visualizer, so you can watch it sort your own numbers one step at a time before you write it yourself.
The roadmap in detail
Everything from the map above, on one page. Dashed topics are optional. The hours are rough estimates for learning, watching the visualizer, implementing the algorithm and solving the problems.
Stage 1 · Beginner Simple sorts
Learn the vocabulary of sorting, then the three O(n²) algorithms. They're too slow for big inputs, but they're easy to follow, and insertion sort is still used inside the fastest real-world sorts.
What sorting is and how to judge a sort
Sorting puts items in order according to a comparison: smaller numbers first, alphabetical names, newest dates. It matters because sorted data is easier to work with: binary search needs it, duplicates end up next to each other, and many problems become a single pass once the data is sorted.
Sorting algorithms are compared by more than speed. Time complexity (best, average and worst case), extra memory (in place or not), stability (do equal items keep their original order?) and adaptivity (is it faster on nearly sorted data?) all matter, and no single algorithm wins on every one.
What to learn
- Ascending vs descending order, and sorting by a key or a custom comparison
- Counting comparisons, swaps and writes as a way to measure cost
- In-place vs out-of-place sorting
- Stable vs unstable sorting, with an example where it matters
- Adaptive sorts and why real data is often partly sorted
Free resources
Practice problems
Build it yourself
Sort a list of people by age with your language's built-in sort, then sort the same list by name and then by age, and check whether people of the same age stay in name order (that's stability).
Tools on this site
Bubble sort
Bubble sort walks through the array comparing each pair of neighbours and swapping them if they're in the wrong order. After the first pass, the largest value has "bubbled" to the end; after the second, the second largest is in place, and so on. If a whole pass makes no swaps, the array is sorted and it can stop early, so it's O(n) on already sorted data but O(n²) otherwise. It's stable and in place, but you'll never use it in real code. Learn it because it's the simplest sort and a good introduction to counting swaps: the number of swaps it makes equals the number of inversions (pairs that are out of order).
What to learn
- The pass structure and why the end of the array becomes sorted first
- The early exit when a pass makes no swaps
- Why it's O(n²) on average and O(n) on sorted input
- Inversions: bubble sort makes exactly one swap per inversion
Free resources
Practice problems
Build it yourself
Implement bubble sort with the early exit and a swap counter. Check that the swap count equals the number of inversions you count with two nested loops.
Tools on this site
Selection sort
Selection sort finds the smallest value in the unsorted part and swaps it to the front, then repeats on the rest. It always makes about n²/2 comparisons, even on sorted data, but never more than n − 1 swaps, which can matter when writes are expensive. The long-distance swap makes it unstable: an equal value can jump over its twin.
What to learn
- The "find the minimum, swap it to the front" loop
- Why the comparison count doesn't depend on the input order
- Why it makes at most n − 1 swaps
- An example input that shows it's unstable
Free resources
Practice problems
Build it yourself
Implement selection sort on records with a name and a value, and find a small input where two equal values end up in a different order from how they started.
Tools on this site
Insertion sort
Insertion sort grows a sorted part on the left. It takes the next value, shifts every larger value in the sorted part one place right, and drops the value into the gap, the way most people sort a hand of cards. Its running time is O(n + inversions): very fast on small or nearly sorted data, O(n²) on random data. That's why Timsort, introsort and pdqsort all switch to insertion sort for short runs of about 16–32 items.
What to learn
- Shifting instead of swapping, and where the held "key" goes
- Why it's stable and in place
- O(n) on sorted input, O(n²) on reversed input, O(n + inversions) in general
- Insertion sort on a linked list
- Why hybrid sorts use it for small subarrays
Free resources
Practice problems
Build it yourself
Time insertion sort against your bubble and selection sorts on 5,000 random, sorted and nearly sorted numbers, and explain the results.
Tools on this site
Am I ready? Stage 1 quiz
What does it mean for a sorting algorithm to be stable?
- It always runs in the same time
- Items with equal keys keep their original relative order
- It never uses extra memory
- It works on any data type
Stability matters when you sort by one field after another, such as by name and then by age.
Which simple sort is fastest on an array that is already almost sorted?
- Selection sort
- Bubble sort without the early exit
- They're all the same
- Insertion sort
Insertion sort does O(n + inversions) work, and a nearly sorted array has very few inversions.
Which algorithm makes the fewest swaps, at most n − 1?
- Selection sort
- Bubble sort
- Insertion sort
- None of them
Selection sort does one swap per position, after finding the minimum. Its comparisons are still O(n²).
After the first pass of bubble sort, what is guaranteed?
- The smallest value is at the front
- The array is half sorted
- The largest value is at the end
- Nothing
The largest value is carried along by every comparison until it reaches the last position.
Bubble sort makes exactly one swap for each…
- Element
- Inversion (a pair of items in the wrong order)
- Pass
- Comparison
Each swap of neighbours fixes exactly one out-of-order pair, so the swap count equals the inversion count.
Stage 2 · Intermediate Divide and conquer
The O(n log n) comparison sorts. Merge sort and quicksort split the problem in two and combine the results; heap sort uses a heap. Quickselect reuses quicksort's partition step to find the k-th smallest value without sorting everything.
Merge sort
Merge sort splits the array in half, sorts each half recursively and merges the two sorted halves by repeatedly taking the smaller front item. There are log₂ n levels of splitting and each level does O(n) merging work, so it's O(n log n) in every case. It's stable (take from the left half on ties) but needs O(n) extra memory for merging. The merge step is useful on its own: merging sorted lists, counting inversions and external sorting all use it.
What to learn
- Top-down (recursive) merge sort and the merge step
- Why it's O(n log n): the recursion tree and the recurrence T(n) = 2T(n/2) + n
- Keeping it stable with
<= in the merge
- Bottom-up (iterative) merge sort
- Merge sort on linked lists (no extra array needed)
- Counting inversions during the merge
Free resources
Practice problems
Build it yourself
Implement merge sort both top-down and bottom-up, add an inversion counter, and check the count against a brute-force O(n²) count on random arrays.
Tools on this site
Quicksort
Quicksort picks a pivot, partitions the array so smaller values are on its left and larger ones on its right, and recursively sorts both sides. The pivot ends up in its final position after each partition. It's in place and usually the fastest sort in practice, but a bad pivot (such as always the last item on already sorted data) gives O(n²). Random pivots or median-of-three make that very unlikely, and three-way partitioning handles many duplicates. It isn't stable.
What to learn
- Lomuto partition (simpler) and Hoare partition (fewer swaps)
- Pivot choice: last item, random, median of three
- Worst case O(n²) and how to avoid it
- Three-way partitioning (Dutch national flag) for duplicates
- Recursion depth: recurse into the smaller side first to keep it O(log n)
Free resources
Practice problems
Build it yourself
Implement quicksort with a last-item pivot and with a random pivot. Count comparisons on sorted input of size 1,000, 2,000 and 4,000 and watch one grow like n² and the other like n log n.
Tools on this site
Quickselect and top-K
To find the k-th smallest value, you don't need to sort. Quickselect partitions like quicksort but only recurses into the side that contains position k, giving O(n) on average. It's the classic answer to "find the k-th largest element" and "find the median". Alternatives: a heap of size k (O(n log k), works on streams) or, when values are small integers, counting. Your language may have it built in, such as C++'s std::nth_element.
What to learn
- Quickselect and why its average time is O(n)
- Random pivots to avoid the O(n²) worst case
- Top-K with a heap vs quickselect vs full sort: when to use which
- Median of medians (guaranteed O(n), mainly of theoretical interest)
Free resources
Practice problems
Build it yourself
Write kth_smallest(a, k) with quickselect and test it against sorted(a)[k] on 10,000 random arrays, including ones full of duplicates.
Tools on this site
Heap sort
Heap sort first turns the array into a max-heap: a binary tree stored in the array (the children of position i are 2i+1 and 2i+2) where every parent is at least as large as its children. The largest value is then at the front. It swaps that value to the end, shrinks the heap by one and "sifts down" the new root to repair it, repeating until the heap is empty. It's O(n log n) in every case with O(1) extra memory, but it isn't stable and is usually slower than quicksort because it jumps around memory.
What to learn
- The array layout of a binary heap
- Sift down and sift up
- Building a heap bottom-up in O(n)
- The two phases of heap sort
- Priority queues: the same structure used for scheduling and Dijkstra
Free resources
Practice problems
Build it yourself
Implement heap sort in place, then print the array after the build phase and check by hand that every parent is at least as large as its children.
Tools on this site
Shell sort
Shell sort speeds up insertion sort by first sorting items that are far apart. It runs insertion sort over every "gap"-th item with a shrinking sequence of gaps, ending with gap 1. Early rounds move values long distances cheaply, so the final insertion sort has little left to do. Its speed depends on the gap sequence: halving (Shell's original) is O(n²) in the worst case, while sequences like Ciura's are much better. It's in place and simple, which made it popular in embedded code.
What to learn
- Gapped insertion sort and h-sorted arrays
- Gap sequences: halving, Knuth (3h + 1) and Ciura
- Why it isn't stable
Free resources
Build it yourself
Implement Shell sort with the halving and Knuth gap sequences and compare their comparison counts on 100,000 random numbers.
Tools on this site
Am I ready? Stage 2 quiz
Why is merge sort O(n log n) in every case?
- It uses a random pivot
- It skips sorted parts
- There are about log n levels of halving, and each level merges n items in total
- It only compares neighbours
The recurrence T(n) = 2T(n/2) + n solves to n log n regardless of the input order.
Quicksort that always uses the last item as the pivot is given an already sorted array. What happens?
- It degrades to O(n²), because every partition is as uneven as possible
- It finishes in O(n)
- It crashes
- Nothing special
Each pivot is the largest value, so one side is empty and the other has n − 1 items. Random pivots avoid this.
What is the average time of quickselect for finding the k-th smallest value?
- O(n log n)
- O(log n)
- O(n²)
- O(n)
It recurses into one side only: n + n/2 + n/4 + … ≈ 2n.
In an array-based heap, where are the children of the item at index i?
- i − 1 and i + 1
- 2i + 1 and 2i + 2
- i / 2 and i / 2 + 1
- Anywhere after i
With 0-based indexing, the children of i are 2i + 1 and 2i + 2, and its parent is (i − 1) / 2.
Which of these sorts is stable?
- Quicksort
- Heap sort
- Merge sort
- Selection sort
Merge sort keeps equal items in order as long as the merge takes from the left half on ties.
Stage 3 · Intermediate Beyond comparisons
Why no comparison sort can beat O(n log n), and the sorts that get around it by looking at the values themselves instead of comparing them.
The O(n log n) lower bound
Any sort that only learns about the data by comparing pairs of items needs at least about n log₂ n comparisons in the worst case. The argument uses a decision tree: each comparison has two outcomes, there are n! possible orders to tell apart, so the tree needs a depth of at least log₂(n!) ≈ n log₂ n. Merge sort and heap sort meet this bound, so they're optimal comparison sorts. Counting, radix and bucket sort are faster in some cases because they don't compare: they use the values as array indices.
What to learn
- The comparison model of computation
- Decision trees and why there are n! leaves
- log₂(n!) ≈ n log₂ n (Stirling's approximation)
- Why non-comparison sorts don't break the bound
Free resources
Practice
Draw the full decision tree for sorting three items a, b and c. Count its leaves (6) and its depth (3), and check that 3 ≥ log₂(6).
Counting sort
Counting sort counts how many times each value appears, then writes the values back in order. It makes no comparisons at all and runs in O(n + k), where k is the range of values (max − min + 1). That's excellent for ages, grades or bytes, and useless when values range over billions. The stable version computes running totals of the counts to find where each value's group starts, then places items in their original order; radix sort depends on this.
What to learn
- Counting occurrences and writing values back
- Handling negative numbers with an offset
- The stable version with prefix sums of counts
- When k makes it impractical
Free resources
Practice problems
Build it yourself
Write a stable counting sort that sorts records (name, score 0–100) by score, and check that records with the same score stay in their input order.
Tools on this site
Radix sort
Radix sort sorts numbers one digit at a time. The usual LSD (least significant digit) version sorts by the ones digit, then the tens, then the hundreds, using a stable counting sort each time. Because each pass keeps the order from the previous one, the array is fully sorted after the last digit. It takes O(d · (n + b)) time for d digits in base b, which beats O(n log n) for many fixed-width integers. It works for strings too: MSD radix sort is how many string sorts and suffix arrays work.
What to learn
- LSD radix sort and why each pass must be stable
- Choosing the base (10 for learning, 256 for bytes in practice)
- Handling negative numbers
- MSD radix sort for strings (overview)
Free resources
Practice problems
Build it yourself
Implement LSD radix sort in base 256 for 32-bit unsigned integers (four passes) and compare it with your language's built-in sort on 10 million numbers.
Tools on this site
Bucket sort
Bucket sort divides the value range into equal-width buckets, drops each item into its bucket, sorts each bucket (usually with insertion sort) and joins them. When values are spread evenly, every bucket is small and the total is O(n + k) on average. When they cluster, one bucket gets everything and it falls back to the speed of the inner sort. The bucketing idea is useful on its own: "Top K frequent elements" and "Maximum gap" both use buckets without sorting at all.
What to learn
- Mapping a value to a bucket index
- Choosing the number of buckets
- Average vs worst case, and what uniform distribution means
- Bucketing by frequency (an array of lists indexed by count)
Free resources
Practice problems
Build it yourself
Bucket-sort 1,000,000 random floats between 0 and 1 using 1,000 buckets, then try numbers where 90% are below 0.01 and measure how much slower it gets.
Tools on this site
Am I ready? Stage 3 quiz
Why can't any comparison sort beat O(n log n) in the worst case?
- Computers are too slow
- It must distinguish n! possible orders with yes/no comparisons, which takes about log₂(n!) ≈ n log n of them
- Recursion has overhead
- Memory is limited
This is the decision-tree argument: a binary tree with n! leaves has depth at least log₂(n!).
When is counting sort a bad choice?
- When there are many duplicates
- When values are small integers
- When the data must be sorted stably
- When the values range over billions
It needs one counter per possible value, so a huge range means huge memory and time.
Why must each digit pass of LSD radix sort be stable?
- So the order from earlier (less significant) digits is kept among items with the same current digit
- To save memory
- Because counting sort is always stable
- It doesn't need to be
Without stability, the tens pass would scramble the ones-digit order of numbers like 21 and 25.
When does bucket sort slow down to its worst case?
- When the input is already sorted
- When there are exactly √n buckets
- When most values fall into the same bucket
- When numbers are negative
Then one bucket holds nearly everything, and the insertion sort inside it is O(n²).
How many comparisons does counting sort make?
- n log n
- None: it uses values as array indices
- n
- n²
That's how it gets around the comparison lower bound.
Stage 4 · Advanced Sorting in practice
How the sorts in your language's standard library really work, how to use them well, and the patterns where sorting turns a hard problem into an easy one. Optional topics cover data too big for memory and sorting in parallel.
Built-in sorts: Timsort, introsort and pdqsort
Real libraries use hybrid sorts. Timsort (Python's sorted, Java's sort for objects) finds already sorted "runs" in the data, extends short ones with insertion sort and merges them, so it's stable and close to O(n) on partly sorted input. Introsort (traditional C++ std::sort) starts with quicksort, switches to heap sort if recursion gets too deep and to insertion sort for small parts. Pattern-defeating quicksort (pdqsort, used by Rust and Go) improves on introsort. Java sorts primitive arrays with a dual-pivot quicksort.
Knowing how to use them matters more than how to write them: sort by a key, sort by several fields, reverse order, and write comparators that are consistent (if a < b and b < c, then a < c), or the sort can misbehave.
What to learn
- Which algorithm your language uses, and whether it's stable
- Sorting by a key and by multiple keys (tuples, chained comparators)
- Writing a correct comparator, and the "largest number" string-comparison trick
- How Timsort uses runs, and why it's fast on real data
- How introsort avoids quicksort's worst case
Free resources
Practice problems
Build it yourself
Write a small hybrid sort: quicksort with a random pivot that switches to insertion sort below 16 items. Find the cut-off that is fastest on your machine.
Tools on this site
Sorting as a problem-solving tool
In interviews, sorting is rarely the question, but it's often the first step of the answer. Sorting intervals by start time lets you merge them in one pass. Sorting by one value and then using a heap or two pointers solves greedy problems such as "boats to save people". Sorting pairs by one dimension turns a 2D problem into a 1D one (Russian Doll Envelopes). If a brute force compares every pair, ask: "would this be easier if the data were sorted?". The O(n log n) cost is usually worth it.
What to learn
- Sort, then a single pass (merging intervals, finding duplicates or gaps)
- Sort, then two pointers (pairs, triples, boats)
- Sort, then a greedy choice (arrows, meetings)
- Sort by one dimension, then solve the other (envelopes, teams)
- Sorting indexes instead of values when you need the original positions
Free resources
Practice problems
Build it yourself
For each problem above, write one sentence saying what you sorted by and why, before you code it. That list is your revision sheet.
Tools on this site
External sorting and k-way merge
When data doesn't fit in memory (say, a 100 GB log file), you sort it in pieces: read a chunk that fits, sort it in memory and write it to disk as a sorted "run", repeat, then k-way merge all runs at once using a min-heap that holds the front item of each run. This external merge sort is how databases sort big tables, how sort on Linux handles huge files, and the core of MapReduce's shuffle step. The same heap-based k-way merge solves many in-memory problems too.
What to learn
- Run generation and the merge phase
- K-way merge with a min-heap in O(n log k)
- Why disk reads and writes, not comparisons, dominate the cost
- Where it's used: databases, Unix
sort, MapReduce
Free resources
Practice problems
Build it yourself
Generate a 1 GB file of random numbers and sort it with a program allowed to hold only 50 MB in memory at a time, then check the output against sort -n.
Sorting networks and parallel sorting
A sorting network is a fixed sequence of compare-and-swap operations that sorts any input of a given size. Because the sequence never depends on the data, many comparisons can run at the same time, which suits GPUs and hardware. Bitonic sort is the best-known example. On ordinary multi-core CPUs, parallel merge sort and sample sort split the work across threads; Java's Arrays.parallelSort and C++'s parallel std::sort do this for you.
What to learn
- Compare-and-swap networks and the 0-1 principle
- Bitonic sort
- Parallel merge sort and sample sort
- Parallel sorts in your language's standard library
Free resources
Build it yourself
Write the optimal 19-comparison sorting network for 8 items and verify it on all 256 inputs of 0s and 1s (the 0-1 principle says that's enough).
Am I ready? Stage 4 quiz
Why is Timsort so fast on real-world data?
- It uses the GPU
- It never compares items
- It detects runs that are already sorted and merges them, so partly sorted data costs close to O(n)
- It's a quicksort with a random pivot
Real data often has sorted stretches. Timsort finds and reuses them instead of starting from scratch.
How does introsort avoid quicksort's O(n²) worst case?
- It switches to heap sort when the recursion gets too deep
- It sorts the array twice
- It uses counting sort for large inputs
- It doesn't; it just hopes
A depth limit of about 2 log n triggers heap sort, guaranteeing O(n log n).
What is the first step to merge overlapping intervals efficiently?
- Build a hash map of starts
- Use a heap of ends
- Compare every pair
- Sort the intervals by start time
After sorting by start, each interval only needs comparing with the last merged one: O(n log n) overall.
You must sort a 500 GB file on a machine with 16 GB of RAM. What do you use?
- Quicksort in memory
- External merge sort: sort chunks that fit in memory, then k-way merge them with a heap
- Counting sort
- Bubble sort, to save memory
External merge sort keeps memory use bounded and reads the data in big sequential passes.
A comparator says a < b, b < c and c < a. What can happen?
- The sort will fix it
- The items are sorted randomly but safely
- The result is unpredictable, and some libraries throw an error
- Nothing, comparators don't need to be consistent
Sorts assume a consistent order. Java's Timsort, for example, may throw "Comparison method violates its general contract!".
How to use this roadmap
- Watch, then write. Open each algorithm in the sorting visualizer, step through it with a few of your own numbers while reading the pseudocode, then close it and implement the algorithm from memory.
- Test against the built-in sort. Run every sort you write on thousands of random arrays (including empty arrays, one item, duplicates and negative numbers) and compare with your language's sort. That catches almost every bug.
- Tick problems as you solve them. Each list goes from easy to hard. Ticking the "What to learn" items tracks the topic itself: ticking the first marks it as in progress, ticking them all marks it as done. Use Export or Share progress to keep your progress.
- Optional topics (dashed borders) don't count towards the percentage.
Which sorting algorithms do I really need to know?
For interviews and exams, know insertion sort, merge sort, quicksort (with partitioning) and heap sort well enough to write them, plus counting sort and the idea of radix sort. Know the complexities and which are stable. Quickselect and "sort first" patterns come up constantly in coding interviews. In day-to-day code, use the built-in sort, but know whether it's stable and how to give it a key or comparator. For the wider picture of data structures and algorithms, continue with the DSA roadmap.