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

Sorting & Searching Beyond the Basics

Every comparison-based sort — merge sort, quicksort, heapsort — is bound by the same hard floor: O(n log n) in the worst case, and no comparison sort will ever beat it. The reason is a counting argument, not an engineering limitation: there are n! possible orderings of n distinct elements, distinguishing between them requires at least log₂(n!) yes/no comparisons in the worst case, and log₂(n!) is itself Θ(n log n). That's why nobody has found a faster general-purpose comparison sort, and why nobody ever will.

Beating O(n log n) with non-comparison sorts

That floor only applies to sorting by comparing elements pairwise. Given extra information about the values — most commonly, that they're integers within a known, reasonably small range — it's possible to sort without a single direct comparison, and legitimately beat O(n log n):

function countingSort(arr, maxValue) {
  const counts = new Array(maxValue + 1).fill(0);
  for (const n of arr) counts[n]++;               // tally how many of each value exist

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

Counting sort runs in O(n + k), where k is the range of possible values — genuinely linear, with zero comparisons — but it's a deliberate trade rather than a free upgrade: it only works when the values are integers in a range small enough to allocate a counts array over, so it's the wrong tool the moment the range is huge or the values aren't integers at all. Radix sort extends the same underlying idea to larger integers by sorting digit by digit, least significant first, using a stable counting sort at each digit position — O(d · (n + k)) for d digits, still without ever comparing two full values directly.

When the built-in sort isn't enough

const people = [{ name: 'Ana', age: 30 }, { name: 'Bo', age: 25 }, { name: 'Cy', age: 30 }];

people.sort((a, b) => a.age - b.age || a.name.localeCompare(b.name));
// primary key: age ascending; tie-break: name alphabetically

A custom comparator is what lets a single .sort() call express a multi-key ordering, ties and all, instead of writing a manual multi-pass sort. It's also worth knowing a genuinely common JavaScript trap here: Array.prototype.sort() called with no comparator sorts elements by converting them to strings first — [10, 2, 1].sort() returns [1, 10, 2], not numeric order — which is a silent, easy-to-miss bug to write under interview pressure. Always pass an explicit numeric comparator when sorting numbers.

Beyond the comparator itself, sometimes the right move is a different data structure entirely rather than repeated sorting: if you need the running top-K as data streams in, a heap (previous chapter) avoids re-sorting the whole collection after every insertion; if you need to repeatedly insert into an already-sorted structure, a balanced BST or similar ordered structure gives O(log n) insertion, against O(n log n) for re-sorting an array from scratch every time.

Practice this on Code Lab: Sorting