Sorting Algorithms
Bubble, selection, insertion, merge and quick sort, animated step by step. Learn which one is stable, which one is in place, and why O(n log n) is the limit for comparison sorts.
Why learn sorting if every language has sort()?
Interviews use sorting to test divide and conquer, partitioning and stability, and many problems become easy once the data is sorted (intervals, two pointers, greedy). You should be able to write merge sort and quick sort from memory and explain their trade-offs.
The algorithms
| Algorithm | Best | Average | Worst | Space | Stable? | Notes |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | ✅ | Teaching only |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | ❌ | Fewest swaps |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | ✅ | Great for small or nearly sorted data |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ | Predictable; used for linked lists and external sorting |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ | Fastest in practice with a random pivot |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ | In place, guaranteed |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(k) | ✅ | Small integer ranges |
Stable means equal keys keep their original order, which matters when you sort by one field after another. Python’s sorted (Timsort) and Java’s object sort are stable; C++ std::sort is not (std::stable_sort is).
Divide and conquer
Merge sort: split in half, sort each half recursively, merge two sorted halves in O(n). The recursion depth is log n and each level does O(n) work, so the total is O(n log n).
Quick sort: choose a pivot, partition so smaller values go left and larger go right, then recurse on both sides. With a bad pivot (already sorted input, last element as pivot) it degrades to O(n²), so pick the pivot at random.
Code template
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]: out.append(left[i]); i += 1
else: out.append(right[j]); j += 1
return out + left[i:] + right[j:]
import random
def quick_sort(a, lo=0, hi=None):
if hi is None: hi = len(a) - 1
if lo >= hi: return
p = random.randint(lo, hi); a[p], a[hi] = a[hi], a[p] # random pivot
pivot, i = a[hi], lo
for j in range(lo, hi):
if a[j] < pivot:
a[i], a[j] = a[j], a[i]; i += 1
a[i], a[hi] = a[hi], a[i]
quick_sort(a, lo, i - 1); quick_sort(a, i + 1, hi)void mergeSort(int[] a, int[] tmp, int lo, int hi) {
if (lo >= hi) return;
int mid = (lo + hi) / 2;
mergeSort(a, tmp, lo, mid); mergeSort(a, tmp, mid + 1, hi);
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (k = lo; k <= hi; k++) a[k] = tmp[k];
}
java.util.Random rnd = new java.util.Random();
void quickSort(int[] a, int lo, int hi) {
if (lo >= hi) return;
int p = lo + rnd.nextInt(hi - lo + 1), t = a[p]; a[p] = a[hi]; a[hi] = t; // random pivot
int pivot = a[hi], i = lo;
for (int j = lo; j < hi; j++) if (a[j] < pivot) { t = a[i]; a[i] = a[j]; a[j] = t; i++; }
t = a[i]; a[i] = a[hi]; a[hi] = t;
quickSort(a, lo, i - 1); quickSort(a, i + 1, hi);
}void mergeSort(vector<int>& a, vector<int>& tmp, int lo, int hi) {
if (lo >= hi) return;
int mid = (lo + hi) / 2;
mergeSort(a, tmp, lo, mid); mergeSort(a, tmp, mid + 1, hi);
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (k = lo; k <= hi; k++) a[k] = tmp[k];
}
void quickSort(vector<int>& a, int lo, int hi) {
if (lo >= hi) return;
swap(a[lo + rand() % (hi - lo + 1)], a[hi]); // random pivot
int pivot = a[hi], i = lo;
for (int j = lo; j < hi; j++) if (a[j] < pivot) swap(a[i++], a[j]);
swap(a[i], a[hi]);
quickSort(a, lo, i - 1); quickSort(a, i + 1, hi);
}function mergeSort(a) {
if (a.length <= 1) return a;
const mid = a.length >> 1, L = mergeSort(a.slice(0, mid)), R = mergeSort(a.slice(mid)), out = [];
let i = 0, j = 0;
while (i < L.length && j < R.length) out.push(L[i] <= R[j] ? L[i++] : R[j++]);
return out.concat(L.slice(i), R.slice(j));
}
function quickSort(a, lo = 0, hi = a.length - 1) {
if (lo >= hi) return;
const p = lo + Math.floor(Math.random() * (hi - lo + 1));
[a[p], a[hi]] = [a[hi], a[p]]; // random pivot
const pivot = a[hi]; let i = lo;
for (let j = lo; j < hi; j++) if (a[j] < pivot) { [a[i], a[j]] = [a[j], a[i]]; i++; }
[a[i], a[hi]] = [a[hi], a[i]];
quickSort(a, lo, i - 1); quickSort(a, i + 1, hi);
}Custom comparators
Many problems are really “sort by the right key”: intervals by start, meetings by end time, the Largest Number problem by a + b > b + a, people by (height desc, k asc).
Practise this pattern (4 problems)
Each problem has a statement, hints, approaches, solutions in 4 languages and a code runner. Solve them in order: easy first.
| # | Problem | Difficulty | |
|---|---|---|---|
| 27 | Sort Colors | Medium | |
| 28 | Merge Intervals | Medium | |
| 29 | Sort an Array | Medium | |
| 30 | Largest Number | Medium |
Common mistakes
- Comparator overflow in Java:
(a, b) -> a - bcan overflow; useInteger.compare(a, b). - Forgetting that sorting costs O(n log n), which may dominate the rest of the solution.
- Using
sort()on numbers in JavaScript without a comparator: it sorts as strings ([10, 9, 1]→[1, 10, 9]).