Compare Sorts Visualization for Coding Interviews
Bubble / Insertion / Merge / Quick / Heap running side-by-side on the same array.
Concept
Comparison-based sorting is the foundation of most day-to-day algorithm work, and picking the right one matters more than the O(n log n) headline suggests. Bubble, insertion, and selection sort are quadratic but have tiny constants and no extra memory, which makes insertion sort the secret weapon inside Timsort and introsort for small runs. Merge sort is the reliable workhorse for stable, predictable behavior with O(n log n) in the worst case but needs O(n) auxiliary space. Quicksort is typically the fastest in practice thanks to cache locality, but its worst case is O(n^2) on adversarial inputs unless the pivot is randomized or median-of-three. Heapsort offers guaranteed O(n log n) with O(1) extra space but loses to quicksort on real hardware due to poor locality. This widget shows them side by side so you can see when each one wins.
How it works
Bubble sort walks the array repeatedly, swapping adjacent out-of-order pairs until a pass completes with no swaps. Insertion sort grows a sorted prefix by taking the next element and shifting it left past larger neighbors until it lands in position — this is why it crushes nearly-sorted input in O(n). Selection sort scans for the minimum of the remaining suffix and swaps it into place; it does O(n^2) comparisons regardless of input. Merge sort divides the array in half recursively, sorts each side, and merges two sorted runs into one with a linear two-pointer pass. Its stability and predictable n log n depth make it the default for linked lists and external sorts. Quicksort picks a pivot, partitions into less-than and greater-than sides (Lomuto or Hoare scheme), and recurses. Hoare partition does fewer swaps on average. Randomizing the pivot or choosing median-of-three keeps the expected depth at log n. Heapsort builds a max-heap in O(n) via sift-down from the middle, then repeatedly swaps the root to the end and sifts down the shrunken heap. It is in-place and worst-case optimal but branchy and cache-unfriendly.
Implementation
import java.util.Arrays;
public final class Sorts {
private Sorts() {}
public static void bubbleSort(int[] a) {
for (int i = a.length - 1; i > 0; i--) {
boolean swapped = false;
for (int j = 0; j < i; j++)
if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = true; }
if (!swapped) return;
}
}
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int x = a[i], j = i - 1;
while (j >= 0 && a[j] > x) { a[j + 1] = a[j]; j--; }
a[j + 1] = x;
}
}
public static void mergeSort(int[] a) {
if (a.length < 2) return;
int[] buf = new int[a.length];
mergeSort(a, buf, 0, a.length - 1);
}
private static void mergeSort(int[] a, int[] buf, int lo, int hi) {
if (lo >= hi) return;
int mid = (lo + hi) >>> 1;
mergeSort(a, buf, lo, mid);
mergeSort(a, buf, mid + 1, hi);
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi) buf[k++] = a[i] <= a[j] ? a[i++] : a[j++];
while (i <= mid) buf[k++] = a[i++];
while (j <= hi) buf[k++] = a[j++];
System.arraycopy(buf, lo, a, lo, hi - lo + 1);
}
public static void quickSort(int[] a) { quickSort(a, 0, a.length - 1); }
private static void quickSort(int[] a, int lo, int hi) {
if (lo >= hi) return;
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++) if (a[j] <= pivot) { i++; int t = a[i]; a[i] = a[j]; a[j] = t; }
int t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
quickSort(a, lo, i);
quickSort(a, i + 2, hi);
}
public static void heapSort(int[] a) {
int n = a.length;
for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
for (int end = n - 1; end > 0; end--) {
int t = a[0]; a[0] = a[end]; a[end] = t;
siftDown(a, 0, end);
}
}
private static void siftDown(int[] a, int i, int n) {
while (true) {
int l = 2 * i + 1, r = l + 1, max = i;
if (l < n && a[l] > a[max]) max = l;
if (r < n && a[r] > a[max]) max = r;
if (max == i) return;
int t = a[i]; a[i] = a[max]; a[max] = t; i = max;
}
}
}
Complexity
- Bubble/Insertion/Selection Time:
O(n^2) - Merge/Heap Time:
O(n log n) - Quick Time (avg/worst):
O(n log n) / O(n^2) - Merge Space:
O(n) - Heap/Quick Space:
O(1) / O(log n)
Common pitfalls
- Using Lomuto quicksort with a last-element pivot on already-sorted input triggers O(n^2).
- Forgetting the stability requirement — quicksort and heapsort are not stable.
- Merging with a fresh buffer per recursion allocates O(n log n) garbage instead of one reused buffer.
- Recursing on the larger quicksort half first can blow the stack on adversarial input.
- Insertion sort is slow only when input is far from sorted — treating it as 'always bad' is wrong.
Key design decisions & trade-offs
- Default in-memory sort — Chosen: Introsort (quick + heap fallback). Average-case speed of quicksort with heap's worst-case guarantee.
- Stable sort requirement — Chosen: Merge sort or Timsort. Quicksort and heapsort reorder equal keys; stability matters when sorting by multiple fields.
- Small arrays (n < 32) — Chosen: Insertion sort. Lower constants and branch-predictable loops beat O(n log n) at small n.
Practice problems
Interview follow-ups
- Implement a hybrid sort that switches to insertion sort for subarrays under 16 elements.
- Add median-of-three pivot selection to quicksort.
- Benchmark these on random, sorted, reverse-sorted, and many-duplicate inputs.
- Build a stable three-way quicksort (Dutch National Flag) for heavy duplicates.
Why it matters
Compare Sorts is a core part of the Sorting toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".