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));
}

Merge sort on index ranges: one buffer, no slices

The merge sort above is the clearest version, but it allocates freely: every call slices out two new arrays and every merge builds a new result, so each level of the recursion copies roughly n elements twice over, about n log n elements allocated over the whole run even though no more than O(n) is alive at once. Interviewers sometimes ask for the version that does not do this, and the next section needs the merge step in a form where you can put a counter inside it. The fix is the same one the recursion chapter used for reverseString: never build a smaller array, pass indices that describe the subproblem, and allocate one scratch buffer up front.

The convention that keeps the arithmetic clean is a half-open range [lo, hi): it includes lo and excludes hi. Its length is hi - lo, a range of length 0 or 1 is already sorted, and the midpoint splits it into [lo, mid) and [mid, hi) with no overlap and no stray + 1 or - 1.

function mergeSortRange(arr) {
  const aux = new Array(arr.length);               // the one scratch buffer, allocated once
  sortRange(arr, aux, 0, arr.length);
  return arr;
}

function sortRange(arr, aux, lo, hi) {              // sorts arr[lo, hi) in place
  if (hi - lo <= 1) return;                        // zero or one element: already sorted
  const mid = lo + ((hi - lo) >> 1);
  sortRange(arr, aux, lo, mid);
  sortRange(arr, aux, mid, hi);
  mergeRange(arr, aux, lo, mid, hi);
}

function mergeRange(arr, aux, lo, mid, hi) {
  for (let k = lo; k < hi; k++) aux[k] = arr[k];   // snapshot the range, so arr can be overwritten
  let i = lo, j = mid;
  for (let k = lo; k < hi; k++) {
    if (i === mid) arr[k] = aux[j++];               // left half used up
    else if (j === hi) arr[k] = aux[i++];           // right half used up
    else if (aux[j] < aux[i]) arr[k] = aux[j++];   // STRICTLY smaller: only then take from the right
    else arr[k] = aux[i++];                         // ties go to the left, which keeps the sort stable
  }
}

Dry run: mergeRange on arr = [2, 5, 8, 3, 4, 9] with lo = 0, mid = 3, hi = 6

The range ends as [2, 3, 4, 5, 8, 9]. The running time is still O(n log n) (n per level, log n levels). Extra space is the single O(n) buffer plus O(log n) of call stack, and nothing else is allocated while the sort runs. Checked against the built-in sort on random arrays, and for stability by sorting records with repeated keys and confirming equal keys kept their original order.

Counting inversions: a merge sort that answers a question

An inversion is a pair of positions i < j with a[i] > a[j]: two elements that are in the wrong order relative to each other. A sorted array has 0, a reversed array of n elements has the maximum, n(n − 1) / 2, and the count measures how far the array is from sorted (it is also the number of swaps of adjacent elements that insertion sort performs). Checking every pair is O(n²). Merge sort gets it in O(n log n) because the merge step already compares elements across the two halves.

Split the array. Every inversion is one of three kinds: both elements in the left half, both in the right, or one in each. The recursion counts the first two kinds. For the third kind, both halves are sorted by the time you merge them, and that is what makes them countable at once. Look at the moment the merge outputs an element from the right half: it is smaller than aux[i], the smallest element left in the left half, and since the left half is sorted it is smaller than every element from aux[i] up to aux[mid - 1]. That is exactly mid - i inversions, all discovered in one step, and each cross-half pair is counted exactly once: when its right-hand element is written. Elements written from the left add nothing.

function countInversions(nums) {
  const arr = nums.slice();                         // the sort reorders its input, so work on a copy
  const aux = new Array(arr.length);

  function sortCount(lo, hi) {                      // sorts arr[lo, hi), returns the inversions inside it
    if (hi - lo <= 1) return 0;
    const mid = lo + ((hi - lo) >> 1);
    let count = sortCount(lo, mid) + sortCount(mid, hi);
    for (let k = lo; k < hi; k++) aux[k] = arr[k];
    let i = lo, j = mid;
    for (let k = lo; k < hi; k++) {
      if (i === mid) arr[k] = aux[j++];
      else if (j === hi) arr[k] = aux[i++];
      else if (aux[j] < aux[i]) {
        arr[k] = aux[j++];
        count += mid - i;                           // jumps over every left element still waiting
      } else arr[k] = aux[i++];
    }
    return count;
  }

  return sortCount(0, arr.length);
}

Dry run: countInversions([2, 4, 1, 3, 5])

By brute force the inversions are (2, 1), (4, 1) and (4, 3): three. The recursion splits [2, 4] from [1, 3, 5]; the smaller pieces [2, 4] and [1, 3, 5] contain none and sort to themselves, so only the top merge counts, with mid = 2:

Writing the 1 jumped over both 2 and 4, which are the pairs (2, 1) and (4, 1); writing the 3 jumped over only the 4, the pair (4, 3). The function returns 3. Time is O(n log n), because the merge does O(n) work per level and the counting adds O(1) to it, and space is O(n) for the copy and the buffer.

A variation: reverse pairs. Count pairs i < j with a[i] > 2 · a[j]. The condition is not the merge order, so you cannot count it inside the merge. But once both halves are sorted, a second pass with two pointers does it: as i moves right through the left half, the right elements it is more than double only grow, so j never moves backwards.

function reversePairs(nums) {
  const arr = nums.slice();
  const aux = new Array(arr.length);

  function sortCount(lo, hi) {
    if (hi - lo <= 1) return 0;
    const mid = lo + ((hi - lo) >> 1);
    let count = sortCount(lo, mid) + sortCount(mid, hi);
    let j = mid;
    for (let i = lo; i < mid; i++) {
      while (j < hi && arr[i] > 2 * arr[j]) j++;   // both halves are sorted: j only moves forward
      count += j - mid;                              // right elements arr[i] is more than double
    }
    mergeRange(arr, aux, lo, mid, hi);              // the plain merge from the previous section
    return count;
  }

  return sortCount(0, arr.length);
}
// reversePairs([1, 3, 2, 3, 1]) → 2    reversePairs([2, 4, 3, 5, 1]) → 3

Both counters were checked against the O(n²) double loop on thousands of random arrays with duplicates and negative values. The same count-while-merging idea answers "count of smaller numbers after self" and "count of range sums" with a little extra bookkeeping, and the divide-and-conquer chapter later in the course builds that out. The shape to remember: if a question is about pairs in the wrong order, ask whether a sorted merge can count them in bulk.

Quicksort — partition, then recurse

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  while (lo < hi) {
    const pivotIndex = partition(arr, lo, hi);
    if (pivotIndex - lo < hi - pivotIndex) { // recurse into the smaller side, loop on the larger:
      quickSort(arr, lo, pivotIndex - 1);   // the stack stays O(log n) however lopsided the splits are
      lo = pivotIndex + 1;
    } else {
      quickSort(arr, pivotIndex + 1, hi);
      hi = pivotIndex - 1;
    }
  }
  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
}

Dry run: partition([8, 2, 9, 1, 5], 0, 4) — 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.

Partitioning: Lomuto's trap, three-way and Hoare

The partition above is Lomuto's scheme: one scanning pointer j, one write pointer i, pivot taken from the end. It is the easiest to write and to explain, and it leaves the pivot at its final position. Its weakness is how it treats elements equal to the pivot: arr[j] < pivot is false for them, so they all pile up on the right. On an array where every element is equal, i never moves, each partition peels off one element and the sort does n(n − 1) / 2 comparisons: 1,999,000 for 2,000 equal values, against 24,320 for 2,000 random ones (both counted). This is not an exotic input. Sorting by a field with a handful of values (a status, a grade, a boolean flag) hands quicksort long runs of equal keys.

Fix 1: three-way partition (the Dutch national flag). Split the range into three blocks, smaller than, equal to, and greater than the pivot value, and then recurse only into the outer two: the whole equal block is already in its final place. Keep four regions as the invariant:

function partition3(arr, lo, hi, pivot) {          // returns [lt, gt]: arr[lt..gt] all equal the pivot
  let lt = lo, i = lo, gt = hi;
  while (i <= gt) {
    if (arr[i] < pivot) {
      [arr[lt], arr[i]] = [arr[i], arr[lt]];        // the element at lt is an "equal": it is safe to move to i
      lt++;
      i++;
    } else if (arr[i] > pivot) {
      [arr[i], arr[gt]] = [arr[gt], arr[i]];
      gt--;                                         // do NOT advance i: the element swapped in is unexamined
    } else {
      i++;
    }
  }
  return [lt, gt];
}

function quickSort3(arr, lo = 0, hi = arr.length - 1) {
  while (lo < hi) {
    const pivot = arr[lo + Math.floor(Math.random() * (hi - lo + 1))];  // random pivot value
    const [lt, gt] = partition3(arr, lo, hi, pivot);
    if (lt - lo < hi - gt) {                       // smaller side by recursion, larger by loop (O(log n) stack)
      quickSort3(arr, lo, lt - 1);
      lo = gt + 1;
    } else {
      quickSort3(arr, gt + 1, hi);
      hi = lt - 1;
    }
  }
  return arr;
}

Dry run: partition3([4, 1, 3, 5, 3, 2, 3], 0, 6, 3)

Now i > gt, so the loop stops with lt = 2 and gt = 4: indices 2 to 4 are the three 3s in their final place, and quicksort only has to sort [1, 2] and [5, 4]. On an all-equal array one pass of n steps leaves lt = lo and gt = hi, so the sort finishes at once (2,000 element visits for 2,000 equal values, instead of 1,999,000 comparisons). The cost is a few more swaps on distinct data, which is why many libraries use the simpler scheme with safeguards instead.

Fix 2: Hoare's scheme, the original two-pointer partition. Pointer i walks right until it meets an element that is not smaller than the pivot, j walks left until it meets one that is not larger, and the two are swapped; this repeats until they cross. Stopping on equal keys looks wasteful, but it is the point: equal keys get swapped, the pointers meet near the middle, and an all-equal array splits evenly (about n log n comparisons, instead of n²). It also tends to do fewer swaps than Lomuto. It is worth knowing exactly, because interviewers like to ask how it differs:

function hoarePartition(arr, lo, hi) {
  const pivot = arr[lo + ((hi - lo) >> 1)];        // middle element, NOT the last one (see the warning)
  let i = lo - 1, j = hi + 1;
  while (true) {
    do i++; while (arr[i] < pivot);                // stops at the first element >= pivot
    do j--; while (arr[j] > pivot);                // stops at the first element <= pivot
    if (i >= j) return j;                          // crossed: [lo..j] <= pivot <= [j+1..hi]
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

function quickSortHoare(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const p = hoarePartition(arr, lo, hi);
  quickSortHoare(arr, lo, p);                       // note: p, not p - 1
  quickSortHoare(arr, p + 1, hi);
  return arr;
}

Quickselect: the k-th smallest without sorting everything

"Find the k-th largest element" does not need a sorted array, only the one element that would sit at a single index. Quicksort recurses into both sides of the pivot; quickselect notices that after a three-way partition it knows exactly where the block equal to the pivot sits, [lt, gt], so for a target index k there are only three cases. If k < lt the answer is in the left part; if k > gt it is in the right part; otherwise k lies inside the equal block and the answer is the pivot itself. Only one part is ever visited, and the other is discarded for good.

function quickselect(nums, k) {                      // k-th smallest, k is 0-based: k = 0 is the minimum
  const arr = nums.slice();                          // leave the caller's array alone
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    const pivot = arr[lo + Math.floor(Math.random() * (hi - lo + 1))];
    const [lt, gt] = partition3(arr, lo, hi, pivot);
    if (k < lt) hi = lt - 1;                        // the answer is among the smaller elements
    else if (k > gt) lo = gt + 1;                   // the answer is among the larger elements
    else return arr[k];                              // k is inside the block equal to the pivot
  }
  return arr[k];                                     // one candidate left
}
// k-th LARGEST with a 1-based k: quickselect(nums, nums.length - k)

Dry run: the 3rd smallest of [7, 2, 9, 4, 1, 8], so k = 2

The sorted array is [1, 2, 4, 7, 8, 9], so the third smallest is 4. Three elements were never touched after round 1. (The pivots are whatever the random choice gives; this trace fixes them to 7 and 4 so it is repeatable, and the function was checked against sorting on thousands of random arrays with many duplicates.)

Why it is O(n) on average. Round one costs n steps. With a random pivot, the pivot's rank lands in the middle half of the values with probability 1/2, and then at most 3n/4 elements remain; otherwise at most n remain. So the expected cost satisfies E(n) ≤ n + ½ · E(3n/4) + ½ · E(n), which rearranges to E(n) ≤ 2n + E(3n/4). Unrolling it gives 2n · (1 + 3/4 + (3/4)² + …) = 8n. That is a safe upper bound; counting actual element visits, finding the median of 100,000 random numbers averaged about 3.4n. The worst case is O(n²), when every pivot is nearly the smallest or largest, which a random pivot makes astronomically unlikely, and an array of equal keys finishes in a single round because k falls inside the equal block. A deterministic O(n) worst case exists (median of medians) but is rarely worth writing in an interview; name it and move on. Space is O(n) for the copy, or O(1) extra if you are allowed to reorder the input.

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

The heaps chapter builds the heap itself, but the sorting 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.

Introsort: how libraries dodge the worst case

Each algorithm so far has a flaw to patch: quicksort can hit O(n²), heapsort is slower in practice, and insertion sort is quick only on small ranges. Introsort (introspective sort) combines all three. It runs quicksort, but counts the recursion depth; once a range has been split more than about 2 · log₂ n levels deep, the splits are evidently bad, so it abandons quicksort on that range and finishes it with heapsort, whose O(n log n) is guaranteed. And ranges that have become small (here 16 elements or fewer) go to insertion sort, which beats everything on tiny inputs. The result runs at quicksort speed on typical data with a worst case of O(n log n); common implementations of C++'s std::sort work this way. JavaScript's .sort() cannot, since it is required to be stable and quicksort and heapsort are not, which is one reason engines use a merge-based hybrid.

function introSort(arr) {
  const limit = 2 * Math.floor(Math.log2(Math.max(arr.length, 1)));
  introRange(arr, 0, arr.length - 1, limit);
  return arr;
}

function introRange(arr, lo, hi, depthLeft) {
  while (hi - lo >= 16) {                                       // big range: partition
    if (depthLeft === 0) { heapSortRange(arr, lo, hi); return; }  // too deep: switch to the guaranteed algorithm
    depthLeft--;
    const [lt, gt] = partition3(arr, lo, hi, medianOfThree(arr, lo, hi));
    if (lt - lo < hi - gt) { introRange(arr, lo, lt - 1, depthLeft); lo = gt + 1; }
    else { introRange(arr, gt + 1, hi, depthLeft); hi = lt - 1; }
  }
  insertionSortRange(arr, lo, hi);                               // small range: insertion sort
}

function medianOfThree(arr, lo, hi) {                            // the median of first, middle and last values
  const a = arr[lo], b = arr[lo + ((hi - lo) >> 1)], c = arr[hi];
  if ((a <= b && b <= c) || (c <= b && b <= a)) return b;
  if ((b <= a && a <= c) || (c <= a && a <= b)) return a;
  return c;
}

function insertionSortRange(arr, lo, hi) {
  for (let i = lo + 1; i <= hi; i++) {
    const current = arr[i];
    let j = i - 1;
    while (j >= lo && arr[j] > current) { arr[j + 1] = arr[j]; j--; }
    arr[j + 1] = current;
  }
}

function heapSortRange(arr, lo, hi) {                            // in-place heapsort of arr[lo..hi]
  const n = hi - lo + 1;
  const siftDown = (root, size) => {
    while (true) {
      let largest = root;
      const left = 2 * root + 1, right = left + 1;
      if (left < size && arr[lo + left] > arr[lo + largest]) largest = left;
      if (right < size && arr[lo + right] > arr[lo + largest]) largest = right;
      if (largest === root) return;
      [arr[lo + root], arr[lo + largest]] = [arr[lo + largest], arr[lo + root]];
      root = largest;
    }
  };
  for (let root = (n >> 1) - 1; root >= 0; root--) siftDown(root, n);   // build the max-heap in O(n)
  for (let end = n - 1; end > 0; end--) {
    [arr[lo], arr[lo + end]] = [arr[lo + end], arr[lo]];                  // largest to the back
    siftDown(0, end);
  }
}

Why the total stays O(n log n): quicksort levels each cost O(n) in total and there are at most 2 log₂ n of them; any range still unsorted at that point is finished by heapsort in O(m log m) for its size m, and those ranges are disjoint, so together they cost at most O(n log n); the insertion-sorted ranges are at most 16 long, so each costs a constant. The function was checked against the built-in sort on thousands of random arrays (small value ranges for duplicates included) and on 100,000-element sorted, reversed, all-equal and alternating inputs, and with depthLeft forced to 0 so that the heapsort path runs on every array. Introsort is not stable.

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.

Writing comparators that do not lie

A comparator (a, b) => number promises three things: a negative number means a goes first, a positive number means b goes first, and zero means they tie. It must also be consistent: if a sorts before b and b before c, then a sorts before c, and swapping the arguments flips the sign. A comparator that breaks this does not fail loudly. The ECMAScript specification leaves the resulting order implementation-defined, so you get a plausible-looking wrong array.

Multi-key sorting: chain the keys with ||

const staff = [
  { name: "Zoe", dept: "ops", salary: 50 },
  { name: "Al",  dept: "eng", salary: 90 },
  { name: "Bo",  dept: "eng", salary: 90 },
  { name: "Cy",  dept: "eng", salary: 70 },
];

staff.sort((a, b) =>
  a.dept.localeCompare(b.dept) ||       // 1st key: department, A to Z
  b.salary - a.salary ||                // 2nd key: salary, highest first (arguments swapped)
  a.name.localeCompare(b.name)          // 3rd key: name, A to Z, breaks the remaining ties
);
// → Al, Bo, Cy (all eng), then Zoe (ops)

The chain works because 0 is falsy: when a key ties, || moves on to the next one, and the first non-zero result wins. Descending order is the same comparison with the arguments swapped (b.salary - a.salary).

Because the sort is stable (the specification requires it since ES2019), there is an alternative: sort by the least important key first, then by the next, ending with the most important. Each later sort keeps the earlier order among ties. One comparator is usually clearer and does one pass.

Comparators that look right and are not

• Returning a boolean. (a, b) => a > b returns true or false, which become 1 and 0 and never a negative number. It cannot say "a goes first". In node, [3, 1, 2].sort((a, b) => a > b) returned [3, 1, 2] unchanged, and 30-element random arrays came out unsorted every time (2,000 of 2,000). Return -1, 0 or 1, or a difference.
• a - b is only a numeric comparator. It works for ordinary numbers: the sign of the difference of two different numbers is always correct. With BigInt it throws TypeError: Cannot convert a BigInt value to a number; use (a < b ? -1 : a > b ? 1 : 0). With NaN or non-numeric strings it returns NaN, which is treated as a tie, so the result is not reliably sorted (in node, [2, 3, NaN, 0, 1] comes back unchanged). (In languages with fixed-width integers, a - b can also overflow, another reason to prefer comparing.)
• Random comparators. sort(() => Math.random() - 0.5) is not a shuffle. For three elements, 120,000 trials gave the order [1, 2, 3] 37.6% of the time and [3, 2, 1] 31.4%, against 16.7% for each if it were uniform. Use Fisher-Yates.
• The default sort. With no comparator, elements are converted to strings and compared by UTF-16 code units: ["file10", "file2", "file1"] sorts to file1, file10, file2, and undefined is always moved to the end without calling your comparator.
• Mutation. sort reorders the array in place and returns that same array. toSorted(compare) (ES2023, available in Node 24) returns a sorted copy and leaves the original alone.

Text: localeCompare and numeric-aware order

Comparing strings with < or the default sort uses code-unit order, so accented letters land after z: ["é", "e", "z", "a"] sorts to a, e, z, é. a.localeCompare(b) follows the locale's dictionary order (here a, e, é, z), and its options include { numeric: true }, which compares embedded digit runs as numbers: ["file10", "file2", "file1"] sorts to file1, file2, file10. The exact order depends on the locale and the engine's ICU data, so for results that must be identical everywhere compare code units on purpose. When sorting many strings, build one Intl.Collator and pass its compare method instead of calling localeCompare on every comparison.

A comparator you must derive: Largest Number

Given non-negative integers, arrange them so that the concatenation is as large as possible: [3, 30, 34, 5, 9] gives "9534330". Sorting the numbers by value or the strings alphabetically fails ("3" versus "30"). What decides whether a belongs before b is simply which concatenation is bigger: a + b or b + a. That is a valid consistent order, so it can be the comparator.

function largestNumber(nums) {
  const parts = nums.map(String);
  parts.sort((a, b) => (b + a < a + b ? -1 : b + a > a + b ? 1 : 0));  // a first when a+b is the bigger string
  return parts[0] === "0" ? "0" : parts.join("");                      // [0, 0] must give "0", not "00"
}

The sorted parts are 9, 5, 34, 3, 30, joined as "9534330". The function matched a try-every-permutation brute force on 1,500 random small inputs that included zeros, repeated values and shared prefixes (12, 121). The comparator compares strings with <, safe here because they contain only digits. Time is O(n log n) comparisons, each costing up to the length of the numbers, and the all-zero case is the edge people forget.

One last performance habit: the comparator is called O(n log n) times, so if it computes something expensive from each element (parse a date, lowercase a long string), compute that key once per element first, sort by the stored keys, then read the elements back (items.map(x => ({ x, key: f(x) })).sort(...).map(e => e.x)).

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));
}

Radix sort: one digit at a time

Counting sort needs a small range, because it allocates one counter per possible value. Integers up to a billion have far too many values for that. Radix sort keeps counting sort's trick of never comparing elements, but applies it to one digit at a time, so each pass needs only ten counters. Process the digits from the least significant to the most significant (LSD radix sort), sorting the whole array by the current digit with a stable counting sort.

Why that ends sorted: after the pass on the ones digit, the array is ordered by its last digit. After the pass on the tens digit, it is ordered by tens, and because the pass is stable, numbers with equal tens digits stay in the order the previous pass gave them, which is ordered by ones. So the array is ordered by the last two digits, and by induction, after the last pass, by the whole number. If any pass were unstable, it would scramble the work of the passes before it.

function radixSort(nums) {                           // non-negative integers
  let out = nums.slice();
  const max = out.reduce((m, x) => Math.max(m, x), 0);
  for (let place = 1; Math.floor(max / place) > 0; place *= 10) {
    const counts = new Array(10).fill(0);
    for (const x of out) counts[Math.floor(x / place) % 10]++;
    for (let d = 1; d < 10; d++) counts[d] += counts[d - 1];   // counts[d] = how many items have digit <= d
    const next = new Array(out.length);
    for (let i = out.length - 1; i >= 0; i--) {                // walk BACKWARDS: that is what keeps the pass stable
      const d = Math.floor(out[i] / place) % 10;
      next[--counts[d]] = out[i];                              // last unfilled slot for this digit
    }
    out = next;
  }
  return out;
}

Dry run: [170, 45, 75, 90, 802, 24, 2, 66]

Look at pass 2: 802 and 2 both have tens digit 0 and keep their pass-1 order (802 before 2), and 24 follows them, then 45, 66, 170 (digit 7) and 75, 90. The loop stops once max / place reaches 0: with a maximum of 802, three passes. The function was checked against the built-in sort on thousands of random arrays with maxima up to 2⁵³ − 1, plus the empty array and arrays of zeros.

Cost. Each pass is O(n + 10), and the number of passes is d, the number of digits of the largest value, so O(d · (n + b)) for base b. For 32-bit integers in base 256 that is 4 passes over the data, which can beat a comparison sort. But the "linear" claim needs d to be a constant. If the values can be as large as n^c, then d grows like log n and the total is again about n log n. Space is O(n) for the output array of each pass (plus O(b) counters).

Why n log n is a wall for comparison sorts

Every sort in the cheat sheet except counting and radix is a comparison sort: it learns about the data only by asking "is a before b?". For those, O(n log n) is not a limitation of the algorithms, it is a theorem, and the argument fits in a paragraph.

Run any comparison sort on an input of n distinct values. Each comparison has two possible answers, so the sequence of answers the algorithm sees can be drawn as a binary decision tree: each internal node is a comparison, each leaf is the final ordering the algorithm outputs. There are n! possible orderings of the input, and a correct algorithm must be able to produce every one of them, so the tree needs at least n! leaves. A binary tree with L leaves has height at least log₂ L, and the height is the number of comparisons on the worst input. So the worst case needs at least log₂(n!) comparisons. To see how big that is without Stirling's formula: the largest n/2 factors of n! are each at least n/2, so n! ≥ (n/2)^n/2 and log₂(n!) ≥ (n/2) · log₂(n/2), which is Ω(n log n).

Merge sort is close to this floor. Its worst case, for the index-range version above, is n⌈log₂ n⌉ − 2^{⌈log₂ n⌉} + 1 comparisons (an exhaustive check over every permutation confirmed this formula for n from 2 to 8), which for n = 1,000 is 8,977, within about 5% of the 8,530 minimum. No comparison sort, however clever, can do asymptotically better.

What the theorem does not say. It bounds the worst case of sorting by comparisons. Insertion sort on a nearly sorted array takes O(n) because that input needs few comparisons to certify. And counting sort and radix sort are not covered at all: they read the values (as array indices and digits) instead of only comparing them, which is exactly why they can run in O(n + k) and O(d · (n + b)). The price is the assumption that values are small integers or fixed-width keys. That is the sentence for the interview: comparison sorting cannot beat n log n, so any faster claim must exploit structure in the data.

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"
• "Number of pairs out of order" or "count pairs where a[i] is more than ... a[j] for i < j" is a merge sort that counts while it merges, not an O(n²) double loop
• "The k-th largest" or "the median" with everything in memory is quickselect (O(n) on average); with a stream or a small k it is a heap
• The ordering is a custom rule ("arrange to form the largest number", "by department, then salary descending"): the work is writing a comparator that is consistent
• The keys are bounded or fixed-width integers and n is large: counting or radix sort, and the n log n bound simply does not apply