Lesson 13 of 2417 min read

Sorting

What the built-in sort actually does, the two algorithms you must be able to write, and the comparator mistake that silently breaks numeric sorts in JavaScript.

By the end: Implement merge sort and quicksort, and sort correctly with the built-in.

In real work you call .sort() and move on. In an interview you need three things: the mistake that breaks JavaScript's built-in sort, the ability to write merge sort and quicksort, and enough knowledge of the alternatives to say why you would not use them.

The bug that catches everyone

Sorting numbers with the default comparator

1
2
3
4const nums = [10, 9, 100, 1, 20];

console.log('default:', [...nums].sort());
console.log('correct:', [...nums].sort((a, b) => a - b));

Output

[1, 10, 100, 20, 9]. The default comparator converts every element to a string and compares text, so '10' comes before '9' because '1' comes before '9'. Always pass a comparator when sorting numbers.

Comparators worth memorising

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23const people = [
  { name: 'Ada', age: 36, dept: 'eng' },
  { name: 'Bo', age: 29, dept: 'design' },
  { name: 'Cy', age: 36, dept: 'design' },
  { name: 'Di', age: 22, dept: 'eng' },
];

console.log('by age:', [...people].sort((a, b) => a.age - b.age).map(p => p.name));
console.log('by age desc:', [...people].sort((a, b) => b.age - a.age).map(p => p.name));
console.log('by name:', [...people].sort((a, b) => a.name.localeCompare(b.name)).map(p => p.name));

// Multiple keys: fall through to the next when the first ties.
const byDeptThenAge = [...people].sort((a, b) =>
  a.dept.localeCompare(b.dept) || a.age - b.age
);
console.log('by dept then age:', byDeptThenAge.map(p => `${p.dept}/${p.age} ${p.name}`));

// Sorting pairs, which comes up constantly with intervals.
console.log('pairs by first then second:',
  [[2, 3], [1, 9], [2, 1], [1, 2]].sort((x, y) => x[0] - y[0] || x[1] - y[1]));

// The boolean bug, shown.
console.log('boolean comparator (wrong):', [3, 1, 2, 5, 4].sort((a, b) => a > b));

Output

Merge sort

Divide and conquer. Split in half, sort each half recursively, then merge the two sorted halves. The merge is the two-pointer technique from lesson 05.

O(n log n) always — best, average and worst. It needs O(n) extra space, and it is stable.

Merge sort, with the recursion shown

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28function mergeSort(arr, depth = 0) {
  const pad = '  '.repeat(depth);
  if (arr.length <= 1) return arr;                    // base case

  const mid = Math.floor(arr.length / 2);
  console.log(`${pad}split [${arr}] into [${arr.slice(0, mid)}] and [${arr.slice(mid)}]`);

  const left = mergeSort(arr.slice(0, mid), depth + 1);
  const right = mergeSort(arr.slice(mid), depth + 1);
  const merged = merge(left, right);

  console.log(`${pad}merged into [${merged}]`);
  return merged;
}

function merge(a, b) {
  const out = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) out.push(a[i++]);      // <= keeps it STABLE
    else out.push(b[j++]);
  }
  while (i < a.length) out.push(a[i++]);
  while (j < b.length) out.push(b[j++]);
  return out;
}

console.log('result:', mergeSort([5, 2, 9, 1, 6]));

Output

Merge sort on real input, and the invariants that matter

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34function merge(a, b) {
  const out = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);
  while (i < a.length) out.push(a[i++]);
  while (j < b.length) out.push(b[j++]);
  return out;
}
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
console.log(mergeSort([]));
console.log(mergeSort([1]));
console.log(mergeSort([2, 1]));
console.log(mergeSort([5, 5, 5]));

// Stability check: sort pairs by the first element only and see whether the
// second elements keep their original relative order.
const pairs = [[1, 'a'], [2, 'b'], [1, 'c'], [2, 'd'], [1, 'e']];
function mergeBy(a, b, key) {
  const out = []; let i = 0, j = 0;
  while (i < a.length && j < b.length) out.push(key(a[i]) <= key(b[j]) ? a[i++] : b[j++]);
  return out.concat(a.slice(i), b.slice(j));
}
function msBy(arr, key) {
  if (arr.length <= 1) return arr;
  const m = Math.floor(arr.length / 2);
  return mergeBy(msBy(arr.slice(0, m), key), msBy(arr.slice(m), key), key);
}
console.log('stable:', msBy(pairs, p => p[0]).map(p => p.join('')).join(' '));

Output

Quicksort

Pick a pivot, partition the array so everything smaller is on the left and everything larger on the right, then sort the two sides. The pivot ends up in its final position, which is the key property.

O(n log n) on average, O(n²) in the worst case, O(log n) stack space, and it sorts in place. Not stable.

Lomuto partition, then quicksort around it

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32// Partition: everything <= pivot moves to the front. Returns the pivot's
// final index. This is the piece worth understanding on its own.
function partition(arr, lo, hi) {
  const pivot = arr[hi];        // choose the last element
  let i = lo;                   // boundary: arr[lo..i-1] are all <= pivot
  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]];    // put the pivot in its place
  return i;
}

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const p = partition(arr, lo, hi);
  quickSort(arr, lo, p - 1);      // pivot is already correct: exclude it
  quickSort(arr, p + 1, hi);
  return arr;
}

console.log(quickSort([5, 2, 9, 1, 6, 3]));
console.log(quickSort([1]));
console.log(quickSort([3, 3, 3]));
console.log(quickSort([5, 4, 3, 2, 1]));

// Watch one partition in isolation.
const demo = [7, 2, 9, 4, 3, 5];
const idx = partition(demo, 0, demo.length - 1);
console.log(`partitioned around 5 → index ${idx}:`, demo, '(left is <= 5, right is > 5)');

Output

Sorted input: naive pivot versus random pivot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32function 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;
}

function quickDepth(arr, lo = 0, hi = arr.length - 1, depth = 0, stats = { max: 0 }) {
  if (lo >= hi) return stats;
  stats.max = Math.max(stats.max, depth);
  const p = partition(arr, lo, hi);
  quickDepth(arr, lo, p - 1, depth + 1, stats);
  quickDepth(arr, p + 1, hi, depth + 1, stats);
  return stats;
}

function quickRandomDepth(arr, lo = 0, hi = arr.length - 1, depth = 0, stats = { max: 0 }) {
  if (lo >= hi) return stats;
  stats.max = Math.max(stats.max, depth);
  const r = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[r], arr[hi]] = [arr[hi], arr[r]];        // swap the random pick to the end
  const p = partition(arr, lo, hi);
  quickRandomDepth(arr, lo, p - 1, depth + 1, stats);
  quickRandomDepth(arr, p + 1, hi, depth + 1, stats);
  return stats;
}

const sorted = Array.from({ length: 200 }, (_, i) => i);
console.log('already sorted, last-element pivot → depth', quickDepth([...sorted]).max, '(bad: about n)');
console.log('already sorted, random pivot       → depth', quickRandomDepth([...sorted]).max, '(good: about log n)');
console.log('log2(200) is about', Math.ceil(Math.log2(200)));

Output

Quickselect: the k-th element without sorting

Partitioning puts one element in its final position. If that position is the one you want, you are done; if not, recurse into only the side that contains your target. That gives O(n) average time to find the k-th smallest, beating a full sort.

Quickselect for the k-th largest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29function 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;
}

// k is 1-based: k = 1 means the largest.
function kthLargest(nums, k) {
  const arr = [...nums];
  const targetIndex = arr.length - k;      // in ascending order
  let lo = 0, hi = arr.length - 1;

  while (lo <= hi) {
    const r = lo + Math.floor(Math.random() * (hi - lo + 1));
    [arr[r], arr[hi]] = [arr[hi], arr[r]];
    const p = partition(arr, lo, hi);

    if (p === targetIndex) return arr[p];
    if (p < targetIndex) lo = p + 1;       // only one side is worth searching
    else hi = p - 1;
  }
  return undefined;
}

console.log('2nd largest of [3,2,1,5,6,4]:', kthLargest([3, 2, 1, 5, 6, 4], 2));   // 5
console.log('4th largest of [3,2,3,1,2,4,5,5,6]:', kthLargest([3,2,3,1,2,4,5,5,6], 4)); // 4
console.log('1st largest:', kthLargest([1], 1));

Output

Counting sort: beating n log n

O(n log n) is the floor for sorts that work by comparing elements. If the values are integers in a small known range you can skip comparisons entirely: count how many of each value there are, then write them out.

Counting sort in O(n + k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27function countingSort(nums, maxValue) {
  const counts = new Array(maxValue + 1).fill(0);
  for (const x of nums) counts[x]++;

  const out = [];
  for (let value = 0; value <= maxValue; value++) {
    for (let i = 0; i < counts[value]; i++) out.push(value);
  }
  return out;
}

console.log(countingSort([4, 2, 2, 8, 3, 3, 1], 8));
console.log(countingSort([1, 1, 1], 1));

// The classic application: sort an array of only 0s, 1s and 2s in one pass,
// in place. This is the Dutch national flag partition.
function sortColors(nums) {
  let low = 0, mid = 0, high = nums.length - 1;
  while (mid <= high) {
    if (nums[mid] === 0) { [nums[low], nums[mid]] = [nums[mid], nums[low]]; low++; mid++; }
    else if (nums[mid] === 2) { [nums[mid], nums[high]] = [nums[high], nums[mid]]; high--; }
    else mid++;
  }
  return nums;
}
console.log('three-way partition:', sortColors([2, 0, 2, 1, 1, 0]));
console.log('three-way partition:', sortColors([2, 0, 1]));

Output

What the built-in actually does

V8 uses TimSort: merge sort with optimisations for data that is already partly ordered, falling back to insertion sort on small runs. It is stable, O(n log n) worst case, and O(n) on nearly-sorted input. You will not beat it by hand, so in real code, use it.

Insertion sort, which is genuinely good on small or nearly-sorted input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15function insertionSort(arr) {
  let shifts = 0;
  for (let i = 1; i < arr.length; i++) {
    const value = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > value) { arr[j + 1] = arr[j]; j--; shifts++; }
    arr[j + 1] = value;
  }
  return { arr, shifts };
}

console.log('random:        ', insertionSort([5, 2, 9, 1, 6]));
console.log('nearly sorted: ', insertionSort([1, 2, 3, 5, 4]));
console.log('already sorted:', insertionSort([1, 2, 3, 4, 5]), '← O(n), zero shifts');
console.log('reversed:      ', insertionSort([5, 4, 3, 2, 1]), '← O(n^2), worst case');

Output

The comparison table

Merge sort — O(n log n) always, O(n) space, stable. Use for linked lists and when worst case matters.
Quicksort — O(n log n) average, O(n²) worst, O(log n) space, not stable, in place. Fastest in practice with a random pivot.
Heap sort — O(n log n) always, O(1) space, not stable. Rarely written by hand; see lesson 16.
Insertion sort — O(n²) worst, O(n) on nearly-sorted, O(1) space, stable. Genuinely best for tiny arrays.
Counting sort — O(n + k), needs integers in a small range. Not a comparison sort, so it beats the n log n bound.
Bubble sort — O(n²). Never use it. Know the name so you can say you would not.

Your turn: four sorting problems

sortByFrequency(nums) — sort so that more frequent values come first; ties broken by the larger value first. Count with a Map, then sort.
largestNumber(nums) — arrange the numbers to form the biggest possible number as a string. [3,30,34,5,9] gives '9534330'. The comparator is the trick: compare b+a with a+b as strings.
mergeKSorted(lists) — merge k sorted arrays. Do it by repeatedly merging pairs, which is O(N log k), rather than one at a time.
countInversions(nums) — how many pairs are out of order. Do it inside a merge sort: when you take an element from the right half, every remaining element in the left half forms an inversion with it.

Editable. Fill them in, then run.

function sortByFrequency(nums) {
  // Map counts, then sort by count desc, then value desc
}

function largestNumber(nums) {
  // map to strings, sort with (a, b) => (b + a).localeCompare(a + b)
}

function mergeKSorted(lists) {
  // pair up and merge repeatedly until one list remains
}

function countInversions(nums) {
  // merge sort, counting left-half remainders when taking from the right
}

console.log(sortByFrequency([1, 1, 2, 2, 2, 3]));        // [2,2,2,1,1,3]
console.log(sortByFrequency([2, 3, 1, 3, 2]));           // [3,3,2,2,1]
console.log(largestNumber([3, 30, 34, 5, 9]));           // '9534330'
console.log(largestNumber([10, 2]));                     // '210'
console.log(mergeKSorted([[1, 4, 5], [1, 3, 4], [2, 6]])); // [1,1,2,3,4,4,5,6]
console.log(countInversions([2, 4, 1, 3, 5]));           // 3
console.log(countInversions([5, 4, 3, 2, 1]));           // 10

Output

Recap

[1,2,3].sort() compares strings: always pass (a, b) => a - b for numbers, and never return a boolean.
Chain comparators with || for multi-key sorts; the built-in sort is stable, which is what makes that work.
Merge sort is O(n log n) always, stable, O(n) space — the safe one to write, and the right one for linked lists.
Quicksort is in place and fastest in practice, but a fixed pivot makes sorted input O(n²); randomise it.
Partitioning gives quickselect for O(n) average top-k, and comparison sorts cannot beat O(n log n) — but counting sort can, when values are small integers.

The bug that catches everyone

Merge sort

Quicksort

Quickselect: the k-th element without sorting

Counting sort: beating n log n

What the built-in actually does

The comparison table

Your turn: four sorting problems

Recap

New writing, when it lands.