Sorting algorithms

The cheat sheet interviewers expect you to know cold

"Stable" means equal elements keep their original relative order — matters when you're sorting objects by one field but want ties to preserve a previous sort order.

Bubble sort — repeatedly swap neighbors into order

The simplest possible sort: walk the array, and whenever two neighbors are out of order, swap them. Repeat full passes until a pass makes zero swaps — that's your signal the array is sorted.

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let swapped = false;
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // already sorted — stop early
  }
  return arr;
}

Notice arr.length - 1 - i: after pass i, the i largest elements are already bubbled to their final spot at the end, so each pass has one less element left to check. That's why it's O(n²) and not O(n³) despite "a pass, repeated n times" sounding like it could be worse.

Selection sort — repeatedly pick the minimum

The mirror image of bubble sort: instead of bubbling large values right via many small swaps, scan the unsorted remainder for its minimum and swap it directly into place — one swap per pass, not many.

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) minIndex = j;
    }
    if (minIndex !== i) [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}

Still O(n²) — finding the minimum is O(n), done n times — but it makes at most n swaps total, versus bubble sort's up to O(n²) swaps. Worth knowing as the answer to "which of these two simple sorts writes to memory less."

Insertion sort — build up a sorted prefix, one element at a time

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j]; // shift bigger elements right
      j--;
    }
    arr[j + 1] = current; // drop it into the gap
  }
  return arr;
}

Merge sort — divide, conquer, then combine

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    result.push(left[i] <= right[j] ? left[i++] : right[j++]);
  }
  return result.concat(left.slice(i), right.slice(j));
}

Quicksort — partition, then recurse

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;

  const pivotIndex = partition(arr, lo, hi);
  quickSort(arr, lo, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, hi);
  return arr;
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i; // pivot's final sorted position
}

Watch one partition pass, step by step

arr = [8, 2, 9, 1, 5], pivot = last element = 5:

After one pass, 5 sits at its final sorted position (index 2), everything smaller is to its left, everything bigger is to its right — and neither side is sorted yet. That's the whole trick: quicksort now recurses on [2, 1] and [8, 9] independently, and the pivot never needs to move again.

Seeing the full recursion tree, not just one level

Both merge sort and quicksort are divide-and-conquer — the diagram earlier only showed one split/merge. Here's why the total work across every level is O(n log n): each level does O(n) work combined (merging, or partitioning), and there are O(log n) levels because the problem size halves each time.

Heap sort — sort using a heap as scratch space

Covered fully in the heaps chapter next, but the shape belongs here too: build a max-heap out of the array in O(n), then repeatedly pull the maximum off the top and place it at the end — O(log n) per extraction, n extractions, O(n log n) total. Unlike merge sort, it sorts in place (O(1) extra space); unlike quicksort, its worst case is guaranteed O(n log n), never O(n²). The tradeoff: it's not stable, and in practice it's usually a bit slower than a well-tuned quicksort due to cache behavior.

Why JS's built-in .sort() usually wins anyway

Array.prototype.sort() defaults to comparing elements as strings — [10, 2, 1].sort() gives [1, 10, 2], not [1, 2, 10], unless you pass a comparator. Always sort numbers with an explicit comparator:

nums.sort((a, b) => a - b);       // ascending
nums.sort((a, b) => b - a);       // descending
people.sort((a, b) => a.age - b.age); // by a field

V8's engine uses TimSort (a hybrid of merge sort and insertion sort) — O(n log n) worst case, and stable. In an interview, you almost never hand-roll a sort; you use it as a fast O(n log n) black box and put your effort into everything around it.

Counting sort — when the range is small

If values are bounded integers in a small known range (say, 0–100), you can sort in O(n + k) instead of O(n log n) by counting occurrences directly instead of comparing elements at all.

function countingSort(arr, maxVal) {
  const counts = new Array(maxVal + 1).fill(0);
  for (const x of arr) counts[x]++;

  const result = [];
  for (let val = 0; val <= maxVal; val++) {
    for (let i = 0; i < counts[val]; i++) result.push(val);
  }
  return result;
}

Bucket sort — counting sort's cousin for spread-out values

When values aren't small integers but are uniformly spread across a known range (e.g. floats between 0 and 1), distribute elements into k buckets by value, sort each small bucket (often with insertion sort, since buckets are tiny), then concatenate. Average case O(n + k); worst case (everything lands in one bucket) degrades to whatever the per-bucket sort costs.

function bucketSort(arr, bucketCount = 10) {
  const buckets = Array.from({ length: bucketCount }, () => []);
  for (const x of arr) {
    const idx = Math.min(bucketCount - 1, Math.floor(x * bucketCount));
    buckets[idx].push(x);
  }
  return buckets.flatMap(bucket => bucket.sort((a, b) => a - b));
}

The decision framework

Recognizing when sorting is the actual pattern

• The problem gets easier once order exists — enables two pointers or binary search
• You need the k-th smallest/largest, or a top-K — sorting is O(n log n), often beaten by a heap (see the heaps chapter)
• Grouping by "same after sorting" (anagrams) — sort each item as a normalizing key
• Interval problems almost always start with "sort by start time"