📈 Algorithms & Complexity
Sorting: from bubble to quicksort
▶ Open the interactive lesson — free, no signupBehind every "sort by price" click on a shopping site and every game leaderboard, one of a handful of classic algorithms is doing the work — and picking the naive one is the difference between the page appearing instantly and a spinner of death.
In this lesson you'll watch five sorts race live on screen, learn why the fast ones win, and find out which one real libraries actually ship.
Sorting is the most-studied problem in computer science — not because sorted data is pretty, but because it unlocks other speed: binary search, spotting duplicates, combining two sorted lists into one, finding the top 10 of anything. And it's the perfect showcase for Big-O, because the gap between the simple Θ(n²) sorts and the clever Θ(n log n) ones is the difference between "instant" and "go get coffee" on real data.
The simple three: Θ(n²) but worth knowing
Bubble sort — swap neighbors until calm
Sweep the array, swapping any adjacent pair that's out of order. Each sweep "bubbles" the largest remaining element to the end. Watch the green sorted zone grow from the right:
▶ This spot has an interactive arrayviz widget — open the interactive lesson to play with it.
#include <stdio.h>
#include <stdbool.h>
void bubble_sort(int *a, int n) {
for (int pass = 0; pass < n - 1; pass++) {
bool swapped = false;
for (int j = 0; j < n - 1 - pass; j++) {
if (a[j] > a[j + 1]) { /* out of order? */
int t = a[j]; /* swap neighbors */
a[j] = a[j + 1];
a[j + 1] = t;
swapped = true;
}
}
if (!swapped) break; /* full pass, no swaps: sorted */
}
}
int main(void) {
int a[] = {5, 1, 4, 2, 8};
bubble_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Insertion sort — how you sort playing cards
Keep the left part sorted; take the next element and slide it left into its place. Crucially, if the data is already nearly sorted, elements barely move — best case Θ(n). Remember that; it matters later.
▶ This spot has an interactive arrayviz widget — open the interactive lesson to play with it.
Selection sort — find the min, swap it home
Scan for the smallest remaining element, swap it into the next position. Simple, and it makes the fewest swaps of any sort (n−1) — but always n(n−1)/2 comparisons, even on sorted input.
▶ This spot has an interactive arrayviz widget — open the interactive lesson to play with it.
void insertion_sort(int *a, int n) {
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { /* shift bigger ones */
a[j + 1] = a[j]; /* one slot right */
j--;
}
a[j + 1] = key; /* drop key in gap */
}
}
void selection_sort(int *a, int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) /* find the smallest */
if (a[j] < a[min]) min = j; /* of the rest */
int t = a[i]; a[i] = a[min]; a[min] = t;
}
}🧠 Checkpoint: You feed an ALREADY-SORTED array to each algorithm. Which finishes in Θ(n)?
- Selection sort
- Insertion sort (and bubble with the early-exit flag)
- Neither — all Θ(n²) sorts stay Θ(n²)
- Only quicksort
Show answer
Insertion sort (and bubble with the early-exit flag) — Insertion sort’s inner while-loop exits immediately when nothing needs shifting: n−1 comparisons total. Bubble with the swapped flag notices the clean pass and stops. Selection sort still scans everything: Θ(n²) always. And sorted input is quicksort’s WORST case with naive pivots!
Quicksort: divide and conquer
The Θ(n²) sorts all share a flaw: they compare elements that tell you almost nothing new. Quicksort's insight (Tony Hoare, 1959) is to make every comparison count. Pick a pivot; partition the array into smaller-than-pivot | pivot | larger-than-pivot. The pivot is now in its final sorted position — recurse on the two sides independently.
▶ This spot has an interactive arrayviz widget — open the interactive lesson to play with it.
#include <stdio.h>
static void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }
/* Lomuto partition: returns the pivot's final index.
Afterwards: a[lo..p-1] < pivot <= a[p+1..hi] */
static int partition(int *a, int lo, int hi) {
int pivot = a[hi]; /* last element as pivot */
int i = lo; /* a[lo..i-1] = smalls */
for (int j = lo; j < hi; j++)
if (a[j] < pivot)
swap(&a[i++], &a[j]); /* grow the smalls zone */
swap(&a[i], &a[hi]); /* pivot between zones */
return i;
}
void quicksort(int *a, int lo, int hi) {
if (lo >= hi) return; /* 0/1 elements: sorted */
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1); /* smalls */
quicksort(a, p + 1, hi); /* bigs (skip the pivot) */
}
int main(void) {
int a[] = {33, 10, 55, 71, 29, 3, 64, 18};
quicksort(a, 0, 7);
for (int i = 0; i < 8; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}$ gcc quicksort.c -o quicksort && ./quicksort 3 10 18 29 33 55 64 71
Each partition pass is Θ(n) work, and a decent pivot splits the array roughly in half, so there are about log₂ n levels of recursion: Θ(n log n) on average. But a terrible pivot (always the smallest or largest element) splits n into 0 and n−1 — that's n levels, and quicksort degrades to Θ(n²).
The classic worst case: with last-element pivots, an already-sorted array is the disaster input — every pivot is the maximum, every split is maximally lopsided. Real implementations dodge this with random or median-of-three pivots. Punchline for interviews: quicksort is Θ(n log n) average, Θ(n²) worst case.
🧠 Checkpoint: With a last-element pivot, which input drives quicksort to its Θ(n²) worst case?
- A random shuffle
- All elements equal to 42… only
- An already-sorted array
- Reverse-sorted arrays only
Show answer
An already-sorted array — Sorted input makes every pivot the largest of its slice: the split is n−1 elements vs 0, recursion depth becomes n, and total work 1+2+…+n = Θ(n²). (Reverse-sorted and all-equal inputs are ALSO degenerate for plain Lomuto — but sorted is the famous, most ironic one: quicksort choking on already-done work.)
Merge sort: guaranteed n log n
Split in half, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front element. Merging is Θ(n), the halving gives exactly log₂ n levels — Θ(n log n) in every case, no bad inputs. The price: it needs a scratch buffer (O(n) extra memory), unlike the in-place sorts above.
#include <stdio.h>
/* sort a[lo..hi) — hi is EXCLUSIVE — using tmp as scratch */
void merge_sort(int *a, int *tmp, int lo, int hi) {
if (hi - lo < 2) return; /* 0/1 element: done */
int mid = lo + (hi - lo) / 2;
merge_sort(a, tmp, lo, mid); /* sort left half */
merge_sort(a, tmp, mid, hi); /* sort right half */
int i = lo, j = mid, k = lo; /* merge: take the */
while (i < mid && j < hi) /* smaller front */
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i < mid) tmp[k++] = a[i++]; /* leftovers */
while (j < hi) tmp[k++] = a[j++];
for (k = lo; k < hi; k++) a[k] = tmp[k];
}
int main(void) {
int a[] = {38, 27, 43, 3, 9, 82, 10};
int tmp[7];
merge_sort(a, tmp, 0, 7);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}$ gcc mergesort.c -o mergesort && ./mergesort 3 9 10 27 38 43 82 # note the <= on the merge comparison: taking from the LEFT # half on ties is exactly what makes merge sort stable.
n² vs n log n — feel the gap
▶ This spot has an interactive bigo widget — open the interactive lesson to play with it.
Stability, and the properties scoreboard
A sort is stable if equal elements keep their original relative order. Sort people by first name, then stably by last name — people with the same last name stay sorted by first name. Non-stable sorts scramble ties, which silently breaks that kind of layered sorting.
| algorithm | best | average | worst | extra space | stable? |
|---|---|---|---|---|---|
| bubble | Θ(n) | Θ(n²) | Θ(n²) | O(1) | yes |
| insertion | Θ(n) | Θ(n²) | Θ(n²) | O(1) | yes |
| selection | Θ(n²) | Θ(n²) | Θ(n²) | O(1) | no |
| quicksort | Θ(n log n) | Θ(n log n) | Θ(n²) | O(log n) stack | no (typical) |
| merge sort | Θ(n log n) | Θ(n log n) | Θ(n log n) | O(n) | yes |
When the "slow" sort wins: for tiny arrays (n ≲ 20) and nearly-sorted data, insertion sort's tiny constant factor and Θ(n) best case beat quicksort's recursive overhead. That's why production sorts (glibc's qsort, C++'s std::sort, Python's Timsort) are hybrids that hand small subarrays to insertion sort. Big-O picks the champion for large n — engineering picks it for your n.
🧠 Checkpoint: You sort records by AGE with a STABLE sort, having already sorted them by NAME. Two people are both 25. Who comes first?
- Unpredictable — ties are arbitrary
- The one whose name sorts first — stability preserves the earlier order
- The one that appeared later in the input
- Stable sorts forbid equal keys
Show answer
The one whose name sorts first — stability preserves the earlier order — Stability means equal-key elements keep their previous relative order — so within each age group, the name ordering survives. This layered-sort trick only works with stable sorts (merge: yes; typical quicksort: no).
In practice: qsort
You met qsort in the stdlib tour — it's how you actually sort in C: generic over element type, driven by your comparison function. (Despite the name, the standard doesn't require quicksort — glibc actually uses merge sort when memory allows!)
#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void *pa, const void *pb) {
int a = *(const int *)pa, b = *(const int *)pb;
return (a > b) - (a < b); /* NEVER a - b: overflow! */
}
int main(void) {
int a[] = {42, 7, 19, 3, 88, 19, 5};
int n = sizeof a / sizeof a[0];
qsort(a, n, sizeof a[0], cmp_int);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}$ gcc use_qsort.c -o use_qsort && ./use_qsort 3 5 7 19 19 42 88
Never write return a - b; in an int comparator: the subtraction can overflow (e.g. INT_MIN − 1), which is undefined behavior and gives garbage orderings. Use the safe idiom (a > b) - (a < b) — it can only produce −1, 0, or +1.
▶ This spot has an interactive editor widget — open the interactive lesson to play with it.
Quicksort and merge sort both leaned on a technique we sneaked past you — a function calling itself. Time to look recursion straight in the eye.
▶ Practice this lesson interactively (with live gcc)