DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Part 15 of 16 · ~4 min

Sorting & Searching Beyond the Basics

Every sort that decides ordering only by comparing two elements at a time runs into the same ceiling, though it's worth pinning down exactly what that ceiling is a statement about. n distinct elements can be arranged n! different ways, and a sequence of true/false comparisons that's supposed to nail down which arrangement you've got needs roughly log₂(n!) of them in the worst case to have enough information to tell every arrangement apart — and that quantity happens to work out to Θ(n log n). It's pure counting, nothing about how cleverly the code is written.

Here's the distinction that's easy to blur, and worth stating carefully: that floor is the best any comparison sort can promise, not a promise every comparison sort keeps. Merge sort and heapsort both guarantee O(n log n) even in the worst case — that's why they're the default safe answer to "what sort should I actually ship." A plain quicksort, run with a fixed pivot choice (the last element, say), makes no such guarantee: feed it an already-sorted array and every partition peels off exactly one element, degrading straight to O(n²). Run a naive quicksort against sorted arrays of 100, 200, and 400 records and count real comparisons, and the pattern gives it away — 4,950, then 19,900, then 79,800, almost exactly quadrupling each time the size doubles, which is quadratic growth, not the roughly 2.3× growth n log n would produce. Randomizing the pivot makes that adversarial case astronomically unlikely — which is exactly why quicksort remains a perfectly sound everyday choice — but "unlikely" and "impossible" are different claims, and the accurate one is that quicksort's worst case is O(n²), with O(n log n) describing its average case only.

Slipping past that floor entirely

The ceiling above only applies to sorts that decide order by comparing values against each other. Know something extra about the values themselves — commonly, that they're whole numbers confined to a small range — and comparison stops being necessary at all, which means the Θ(n log n) floor simply doesn't apply anymore. Exam scores are the textbook case: always integers, always somewhere from 0 to 100.

function countingSortScores(scores) {
  const counts = new Array(101).fill(0);          // one bucket for each possible score
  for (const s of scores) counts[s]++;

  const sorted = [];
  for (let score = 0; score <= 100; score++) {
    for (let i = 0; i < counts[score]; i++) sorted.push(score);   // emit each score that many times
  }
  return sorted;
}

The cost is O(n + k), with k standing for how wide the value range is — a genuinely linear pass, no comparisons anywhere in it — but this isn't a free win, it's a trade with a specific price tag. It depends entirely on the values being integers spread across a range small enough that allocating one bucket per possible value is affordable, so the trick disappears the moment scores stop being a tidy 0-through-100 scale and start being open-ended point totals instead. For integers too big to bucket directly, radix sort applies the same trick digit by digit instead of value by value — sort on the ones place, then the tens place, then the hundreds, working outward from the least significant digit, using counting sort's bucketing at each pass. d passes over n values with a range-k bucket each time comes to O(d · (n + k)), and it's still comparison-free throughout. A large batch of student ID numbers is exactly the kind of input this is built for.

When the built-in sort isn't enough

The waitlist needs a genuine multi-key order — priority tier first, earliest request wins ties within a tier:

const waitlist = [
  { name: 'Priya', tier: 2, requestedAt: 104 },
  { name: 'Marco', tier: 1, requestedAt: 210 },
  { name: 'Wei',   tier: 1, requestedAt: 98 },
];

waitlist.sort((a, b) => a.tier - b.tier || a.requestedAt - b.requestedAt);
// primary key: tier ascending; tie-break: earlier request wins

A custom comparator turns one .sort() call into a full multi-key ordering, ties included, without a manual multi-pass sort. Right next to that convenience sits a trap plenty of JavaScript developers fall into more than once: call .sort() with no comparator at all, and it converts every element to a string before comparing. Three waitlist counts — [25, 5, 100] — look like they belong in numeric order [5, 25, 100], but a bare .sort() compares the text "100", "25", "5", and text starting with "1" sorts before text starting with "2" or "5" — landing on [100, 25, 5], the opposite of what numeric order would give. That's a quiet, easy bug to write with a clock running. Pass an explicit numeric comparator any time the values being sorted are numbers.

Beyond writing a better comparator, the real fix is occasionally to stop sorting repeatedly and switch structures instead. A running top-K as demand streams in belongs to a heap (previous chapter), which sidesteps a full re-sort after every update. Repeatedly inserting into a waitlist that has to stay sorted belongs to a balanced BST or an equivalent ordered structure — each insertion costs O(log n) there, against the O(n log n) price of throwing the array away and rebuilding it sorted from nothing every time a name gets added.

Sorting on Code Lab.