Sorting
Insertion, merge and quick sort compared, plus stability, why comparison sorts need n log n, and when counting sort beats them.
intermediate50 min#sorting#merge-sort#quicksort#stability#counting-sort
Prerequisites: Arrays and Dynamic Arrays, Recursion, Big-O and Complexity Analysis
Why it matters
Sorted data unlocks binary search, fast duplicate detection, merging, interval problems and many greedy algorithms. Sorting is also the cleanest place to compare algorithm design ideas: incremental building, divide and conquer, in-place partitioning, and non-comparison tricks. In practice you will almost always call the library sort, so the goal is to know what it guarantees (such as stability) and to recognize when a problem is secretly "sort, then scan".
Intuition
Sorting a hand of playing cards, you pick up one card at a time and slide it left into place among the cards you already hold. That is insertion sort. Alternatively, split the deck in halves, sort each half, then interleave two sorted piles by repeatedly taking the smaller top card. That is merge sort. Or pick a card (the pivot), put smaller cards on its left and larger on its right, and repeat on each side. That is quick sort.
How it works
Insertion sort. Keep a sorted prefix; insert the next item by shifting larger items right. O(n^2) worst case, but O(n) on nearly sorted data and very low overhead, so real libraries use it for tiny ranges.
Step through insertion sort on [5, 2, 9, 1]. Amber cells are the sorted prefix and the green cell is the item being inserted.
Insertion sort grows a sorted prefix, shifting larger items right to open a slot for each new item.
Merge sort. Split in half, sort each half recursively, merge. Merging two sorted lists takes one linear pass. The recursion has log n levels and each level does O(n) work, so it is O(n log n) in every case. It needs O(n) extra space for the merge, and it is stable.
Merge sort on [5, 2, 9, 1] as a tree: first split down to single items, then merge back up. Click through it.
Splitting is free; all the work happens in the merges, and each level of the tree merges n items in total.
[5 2 9 1]
/ \
[5 2] [9 1] split until size 1
[5][2] [9][1]
\ / \ /
[2 5] [1 9] merge sorted pairs
\ /
[1 2 5 9]
Quick sort. Choose a pivot, partition so smaller items go left and larger go right (the pivot is now in its final position), then recurse on both sides. Average O(n log n) and sorts in place with small constants, which is why it is fast in practice. The worst case is O(n^2), when pivots are consistently the smallest or largest (for example always picking the first item of already sorted data). Choosing a middle or random pivot, or a median of three, makes that unlikely. It is not stable.
Here is one partition from the code below on [5, 2, 9, 1, 5, 6, 0, 3]. The middle item (index 3, value 1) is the pivot. p marks where the next smaller item will go, and i is the scan position.
Partition makes one pass and puts the pivot in its final sorted position. This pivot was unlucky (one item on its left), so the split is uneven.
Heap sort. Build a heap, then repeatedly remove the maximum. O(n log n) worst case, in place, not stable, and slower in practice because of poor cache behavior. Introsort (used by several C++ libraries) starts with quick sort and falls back to heap sort if recursion gets too deep, to guarantee O(n log n).
Stability. A sort is stable if items with equal keys keep their original relative order. This matters when you sort by multiple keys in passes (sort by name, then stable sort by age, and ties in age stay alphabetical). Merge sort and insertion sort are stable; quick sort and heap sort are not, in their usual forms. Python's sorted (Timsort, a merge and insertion hybrid) is stable, and Array.prototype.sort in JavaScript is required to be stable since ES2019.
The comparison lower bound. Any algorithm that sorts only by comparing pairs must distinguish among n! possible orderings; each comparison gives one bit, so at least log2(n!), roughly n log n, comparisons are needed. You cannot beat O(n log n) with comparisons alone.
Counting sort breaks the bound by not comparing. If keys are integers in a small range 0..k, count how many times each appears, then rebuild the output. O(n + k) time, O(k) space. Radix sort extends this to larger keys, one digit at a time. The price is that it only works for suitable keys and the range must be small relative to n.
The reason the O(n log n) sorts matter is how fast the two cost curves pull apart as n grows.
For a concrete size, here is the rough number of basic steps to sort one million items (log scale, since the bars differ by a factor of about 50,000).
| Operation | Time | Notes |
|---|---|---|
| Insertion sort | O(n^2) worst, O(n) nearly sorted | Stable, in place |
| Merge sort | O(n log n) always | Stable, O(n) extra space |
| Quick sort | O(n log n) average, O(n^2) worst | In place, not stable |
| Heap sort | O(n log n) always | In place, not stable |
| Counting sort | O(n + k) | Integer keys in range 0..k |
| Library sort (Timsort) | O(n log n) worst, O(n) if already sorted | Stable |
Code: four sorts and a stability check
def insertion_sort(a):
a = list(a)
for i in range(1, len(a)):
x, j = a[i], i - 1
while j >= 0 and a[j] > x: # strict > keeps equal items in order
a[j + 1] = a[j]
j -= 1
a[j + 1] = x
return a
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= on ties takes the left item: stable
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]
def quick_sort(a, lo=0, hi=None):
"""In-place quicksort, Lomuto partition with a middle pivot."""
if hi is None:
hi = len(a) - 1
if lo >= hi:
return a
mid = (lo + hi) // 2
a[mid], a[hi] = a[hi], a[mid] # move pivot to the end
pivot, p = a[hi], lo
for i in range(lo, hi):
if a[i] < pivot:
a[i], a[p] = a[p], a[i]
p += 1
a[p], a[hi] = a[hi], a[p] # pivot lands in its final spot
quick_sort(a, lo, p - 1)
quick_sort(a, p + 1, hi)
return a
def counting_sort(a, max_value):
counts = [0] * (max_value + 1)
for x in a:
counts[x] += 1
out = []
for value, c in enumerate(counts):
out.extend([value] * c)
return out
data = [5, 2, 9, 1, 5, 6, 0, 3]
print(insertion_sort(data))
print(merge_sort(data))
print(quick_sort(list(data)))
print(counting_sort(data, 9))
people = [("Ana", 30), ("Bo", 25), ("Cy", 30), ("Di", 25)]
by_age = sorted(people, key=lambda p: p[1]) # stable: ties keep input order
print([name for name, _ in by_age])function insertionSort(input) {
const a = [...input];
for (let i = 1; i < a.length; i++) {
const x = a[i];
let j = i - 1;
while (j >= 0 && a[j] > x) {
// strict > keeps equal items in order
a[j + 1] = a[j];
j--;
}
a[j + 1] = x;
}
return a;
}
function mergeSort(a) {
if (a.length <= 1) return a;
const mid = Math.floor(a.length / 2);
const left = mergeSort(a.slice(0, mid));
const right = mergeSort(a.slice(mid));
const out = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
// <= on ties takes the left item: stable
if (left[i] <= right[j]) out.push(left[i++]);
else out.push(right[j++]);
}
return out.concat(left.slice(i), right.slice(j));
}
// In-place quicksort, Lomuto partition with a middle pivot.
function quickSort(a, lo = 0, hi = a.length - 1) {
if (lo >= hi) return a;
const mid = Math.floor((lo + hi) / 2);
[a[mid], a[hi]] = [a[hi], a[mid]]; // move pivot to the end
const pivot = a[hi];
let p = lo;
for (let i = lo; i < hi; i++) {
if (a[i] < pivot) {
[a[i], a[p]] = [a[p], a[i]];
p++;
}
}
[a[p], a[hi]] = [a[hi], a[p]]; // pivot lands in its final spot
quickSort(a, lo, p - 1);
quickSort(a, p + 1, hi);
return a;
}
function countingSort(a, maxValue) {
const counts = new Array(maxValue + 1).fill(0);
for (const x of a) counts[x]++;
const out = [];
counts.forEach((c, value) => {
for (let k = 0; k < c; k++) out.push(value);
});
return out;
}
const fmt = (xs) => "[" + xs.join(", ") + "]";
const data = [5, 2, 9, 1, 5, 6, 0, 3];
console.log(fmt(insertionSort(data)));
console.log(fmt(mergeSort(data)));
console.log(fmt(quickSort([...data])));
console.log(fmt(countingSort(data, 9)));
const people = [["Ana", 30], ["Bo", 25], ["Cy", 30], ["Di", 25]];
const byAge = [...people].sort((p, q) => p[1] - q[1]); // stable since ES2019
console.log("[" + byAge.map(([name]) => `'${name}'`).join(", ") + "]");Both versions print:
[0, 1, 2, 3, 5, 5, 6, 9]
[0, 1, 2, 3, 5, 5, 6, 9]
[0, 1, 2, 3, 5, 5, 6, 9]
[0, 1, 2, 3, 5, 5, 6, 9]
['Bo', 'Di', 'Ana', 'Cy']
The four sorted lists come from insertion, merge, quick and counting sort. On the last line, sorting by age leaves Bo before Di (both 25) and Ana before Cy (both 30), the same order as in the input, which demonstrates stability.
Common pitfalls
- Bad comparators: a comparator must be consistent (if a is before b then b is not before a). Returning a boolean from a JavaScript comparator, or subtracting values that can overflow or be
NaN, gives undefined ordering. - Quick sort worst case: first or last pivot on sorted input is O(n^2) and recursion depth O(n). Pick the pivot more carefully and recurse into the smaller side first.
- Sorting in place by accident:
list.sort()andarray.sort()mutate and return nothing useful (or the same array). Usesorted(...)or[...a].sort(...)to keep the original. - Assuming stability: if equal keys must keep their order, check your tool guarantees it.
- Using counting sort on a huge range: with a key up to 10^9 and only 1000 items, the count array is enormous. Use a comparison sort.
- Sorting when you do not need to: finding the maximum is O(n); finding the k largest can use a heap in O(n log k).
Practice
Merge two sorted arrays easy
Hint
Use one index per array and always take the smaller current item. This is the merge step.
Show solution
Walk both arrays with indexes i and j, appending the smaller item (on ties take from the first for stability). When one array ends, append the rest of the other. O(n + m) time.
Sort colors (Dutch national flag) medium
Hint
Only three values. You can do it in one pass with three regions.
Show solution
Keep lo, mid and hi. If a[mid] is 0, swap it with a[lo] and advance both; if 1, advance mid; if 2, swap with a[hi] and decrease hi without advancing mid (the swapped item is unexamined). One pass, O(n) time, O(1) space. This is a three-way partition, also the basis of quick sort variants that handle many duplicates well.
Merge overlapping intervals medium
Hint
After sorting by start, which intervals can possibly overlap with the current one?
Show solution
Sort by start. Keep a result list; for each interval, if its start is at most the end of the last merged interval, extend that end to the larger of the two; otherwise append it. O(n log n) for the sort, O(n) for the scan. Sorting turns a pairwise problem into a single pass.
Kth largest element hard
Hint
A full sort works. Can you do better by only partially ordering the data, using the quick sort partition or a heap?
Show solution
Sorting gives O(n log n). Quickselect partitions like quick sort but recurses into only the side that contains index n - k, giving O(n) average and O(n^2) worst case. A min-heap of size k gives O(n log k) and works on streams. Mention the trade-offs and pick based on constraints.
Interview questions
- Why is merge sort O(n log n) always but quick sort is not? Merge sort splits exactly in half; quick sort splits wherever the pivot lands, which can be badly unbalanced.
- What does stable mean and why care? Equal keys keep their input order, which makes multi-key sorting by successive passes correct.
- Can you sort faster than n log n? Not by comparison. With bounded integer keys, counting or radix sort can reach linear time.
- When would you pick insertion sort? Very small or nearly sorted inputs, where its low overhead wins; many libraries use it as the base case of a faster sort.
- How much extra memory does each use? Merge sort O(n), quick sort O(log n) stack on average, heap and insertion sort O(1).
Interviewers look for: asking about size, duplicates and stability needs, naming quick sort's worst case and the fix, and knowing that the built-in sort is usually the right production choice.
Quick check
You must sort records by (department, then name) using two passes of a stable sort. Which order of passes is correct?
Finished this lesson?
Further resources
- Sorting algorithm (Wikipedia) (article)
- Python HOWTO: Sorting (docs)
- MDN: Array.prototype.sort() (docs)
- Quicksort (Wikipedia) (article)