Sorting

Table of Contents

1. Why Sort at All
2. Bubble Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort
6. Stability
7. Array.sort and the Default-String Trap
8. Counting Sort and the O(n log n) Limit
9. Benchmark
10. Recipe: sorting.ts for algolab
11. Try It Yourself

1. Why Sort at All

Sorting is rarely the goal. It is a preparation step that makes other things cheap:

• Binary search (last chapter) needs sorted data.
• Finding duplicates becomes easy: equal items end up next to each other.
• Merging two sorted lists takes one pass.
• People expect sorted output: products by price, messages by date, a leaderboard by score.

In daily work you will almost always call the built-in array.sort(). So why learn to write one? Three reasons. First, sorting is the cleanest place to see how different algorithms trade speed, memory, and simplicity. Second, the ideas inside merge sort and quick sort (divide and conquer) show up again in trees, heaps, and dynamic programming. Third, interviewers ask about it, and the built-in has sharp edges (section 7) that every JavaScript developer needs to know.

The sorts in this chapter fall into two families:

Remember from the Big-O chapter what that gap means: for 1,000,000 items, n² is a trillion steps while n log n is about 20 million.

All our sorts follow one convention. They take a compare(a, b) function that returns a negative number if a should come first, a positive number if b should come first, and 0 if they tie. This is the same contract Array.prototype.sort uses. And they return a new array rather than changing the input, which is safer.

2. Bubble Sort

Walk through the array and compare each neighbouring pair. If a pair is out of order, swap it. After one full pass the biggest item has "bubbled" to the end. Repeat for the rest.

One pass on [5, 1, 4, 2, 8]:

[5, 1, 4, 2, 8]   compare 5,1 -> swap
[1, 5, 4, 2, 8]   compare 5,4 -> swap
[1, 4, 5, 2, 8]   compare 5,2 -> swap
[1, 4, 2, 5, 8]   compare 5,8 -> fine

The 8 was already in place, and the 5 moved next to it. Each later pass fixes one more item at the end:

type Compare<T> = (a: T, b: T) => number;

const byDefault = <T>(a: T, b: T): number => (a < b ? -1 : a > b ? 1 : 0);

function bubbleSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  const a = [...items]; // work on a copy

  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;

    for (let i = 0; i < a.length - 1 - pass; i++) {
      if (compare(a[i], a[i + 1]) > 0) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }

    if (!swapped) break; // no swaps means already sorted
  }

  return a;
}

console.log(bubbleSort([5, 2, 9, 1, 5, 6])); // [ 1, 2, 5, 5, 6, 9 ]

The - pass in the inner loop skips the tail that is already fixed. The swapped flag gives an early exit: on already-sorted input, one pass finds nothing to swap and stops, so the best case is O(n).

The worst and average cases are O(n²): about n passes of about n comparisons each. Bubble sort is mostly a teaching tool. It is easy to understand but slow, and no real library uses it.

3. Insertion Sort

Think of sorting playing cards in your hand. You pick up one card at a time and slide it left into the right place among the cards you already hold.

[5, 2, 4, 1]
 i=1: take 2, shift 5 right        -> [2, 5, 4, 1]
 i=2: take 4, shift 5 right        -> [2, 4, 5, 1]
 i=3: take 1, shift 5, 4, 2 right  -> [1, 2, 4, 5]

function insertionSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  const a = [...items];

  for (let i = 1; i < a.length; i++) {
    const current = a[i];
    let j = i - 1;

    // shift bigger items one step right to open a gap
    while (j >= 0 && compare(a[j], current) > 0) {
      a[j + 1] = a[j];
      j--;
    }

    a[j + 1] = current; // drop it into the gap
  }

  return a;
}

console.log(insertionSort([5, 2, 9, 1, 5, 6])); // [ 1, 2, 5, 5, 6, 9 ]

Everything left of i is always sorted (this is the invariant, the fact that stays true on every loop). Each new item is inserted to keep it true.

Worst case (reverse order) is O(n²). But insertion sort has a real strength: on data that is already nearly sorted it is close to O(n), because each item only moves a step or two. It also has almost no overhead. That is why serious sorting algorithms, including the one inside V8, switch to insertion sort for tiny slices.

4. Merge Sort

Merge sort uses divide and conquer: split the problem in half, solve each half, combine the answers. For sorting:

1. Split the array into a left half and a right half.
2. Sort each half (by calling merge sort again, which is recursion).
3. Merge the two sorted halves into one sorted array.

The base case is an array of 0 or 1 items, which is already sorted.

The magic is in the merge step. Merging two sorted lists is easy: keep a pointer in each, repeatedly take the smaller front item. Merging [1, 4, 7] and [2, 3, 9]:

left [1,4,7]   right [2,3,9]   take 1 -> [1]
left [4,7]     right [2,3,9]   take 2 -> [1,2]
left [4,7]     right [3,9]     take 3 -> [1,2,3]
left [4,7]     right [9]       take 4 -> [1,2,3,4]
left [7]       right [9]       take 7 -> [1,2,3,4,7]
left []        right [9]       copy 9 -> [1,2,3,4,7,9]

function mergeSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  if (items.length <= 1) return [...items];

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

  return merge(left, right, compare);
}

function merge<T>(left: T[], right: T[], compare: Compare<T>): T[] {
  const out: T[] = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    // <= takes from the left on ties, which keeps the sort stable
    if (compare(left[i], right[j]) <= 0) out.push(left[i++]);
    else out.push(right[j++]);
  }

  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);

  return out;
}

console.log(mergeSort([5, 2, 9, 1, 5, 6])); // [ 1, 2, 5, 5, 6, 9 ]

Why O(n log n)? Halving an array of n items takes about log₂ n levels, because you can only halve so many times. At every level, the merges together touch each of the n items once. So the total is n × log n:

level 0:  [ 8 items ]                  merge work: 8
level 1:  [ 4 ]   [ 4 ]                merge work: 8
level 2:  [2] [2] [2] [2]              merge work: 8
level 3:  [1][1][1][1][1][1][1][1]     merge work: 8

Three splits, each level costing 8 units of work: 8 × log₂ 8 = 24. For a million items, 20 levels. Importantly, this holds in every case: sorted, reversed, or random input all cost O(n log n).

The price is memory. Merge sort needs O(n) extra space for the temporary arrays. Its big advantages are the guaranteed speed and that it is stable (section 6).

5. Quick Sort

Quick sort also divides and conquers, but does the work before recursing instead of after:

1. Pick one item as the pivot.
2. Partition: rearrange so every item smaller than the pivot is on its left and every bigger item is on its right. Now the pivot is in its final position.
3. Recursively sort the left part and the right part.

There is no merge step, so quick sort can work in place with only O(log n) extra space for the recursion. In practice it is often the fastest of all general-purpose sorts, because it touches memory in a cache-friendly way.

The partition step is the clever part. We use the Lomuto scheme: put the pivot at the end, keep a boundary i between "smaller than pivot" and "the rest", and sweep j through the range:

function quickSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  const a = [...items];
  sortRange(a, 0, a.length - 1, compare);
  return a;
}

function sortRange<T>(a: T[], lo: number, hi: number, compare: Compare<T>): void {
  while (lo < hi) {
    const p = partition(a, lo, hi, compare);

    // recurse into the smaller side, loop on the larger side,
    // so the call stack never grows deeper than log n
    if (p - lo < hi - p) {
      sortRange(a, lo, p - 1, compare);
      lo = p + 1;
    } else {
      sortRange(a, p + 1, hi, compare);
      hi = p - 1;
    }
  }
}

function partition<T>(a: T[], lo: number, hi: number, compare: Compare<T>): number {
  // random pivot, moved to the end
  const r = lo + Math.floor(Math.random() * (hi - lo + 1));
  [a[r], a[hi]] = [a[hi], a[r]];
  const pivot = a[hi];

  let i = lo; // everything in [lo, i) is smaller than the pivot
  for (let j = lo; j < hi; j++) {
    if (compare(a[j], pivot) < 0) {
      [a[i], a[j]] = [a[j], a[i]];
      i++;
    }
  }

  [a[i], a[hi]] = [a[hi], a[i]]; // pivot goes to its final spot
  return i;
}

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

Partitioning [3, 8, 1, 5] with pivot 5 (already at the end):

i=0, j=0: 3 < 5 -> swap a[0] with itself, i=1     [3, 8, 1, 5]
i=1, j=1: 8 < 5? no                               [3, 8, 1, 5]
i=1, j=2: 1 < 5 -> swap a[1] and a[2], i=2        [3, 1, 8, 5]
finish:   swap a[2] and the pivot                 [3, 1, 5, 8]

The pivot 5 sits at index 2, everything left is smaller, everything right is bigger.

Choosing the pivot matters. If you always pick the last item and the input is already sorted, each partition peels off just one item, giving O(n²). That is why we pick a random pivot: no particular input is reliably bad. Then the average case is O(n log n), and the worst case becomes so unlikely that you can ignore it.

One weakness remains. Our partition treats items equal to the pivot as "not smaller", so they all land on the right side. If the array holds many duplicates, the split becomes badly lopsided. In a test run, our quickSort on 50,000 identical numbers took more than a second, while a random array of that size sorts in a few milliseconds. Real implementations fix this with a three-way partition (smaller, equal, bigger). You will do exactly that in exercise 4.

6. Stability

A sort is stable if items that compare as equal keep their original relative order. This sounds like a detail, but it matters whenever you sort by more than one field.

Imagine a table of people already sorted by name. The user then clicks "sort by age". With a stable sort, people of the same age remain in name order. With an unstable one they get shuffled.

const people = [
  { name: "A", age: 30 },
  { name: "B", age: 25 },
  { name: "C", age: 30 },
  { name: "D", age: 25 },
];

const byAge = (x: { age: number }, y: { age: number }) => x.age - y.age;

console.log(mergeSort(people, byAge).map((p) => p.name).join(""));
// BDAC   (B before D, A before C: original order kept inside each age)

Insertion sort and bubble sort are stable too (they only swap items that are strictly out of order). Our merge sort is stable because of the <= in merge: on a tie it takes from the left, which came first. Our quick sort is not stable, because partition jumps items across each other.

Since ES2019, Array.prototype.sort in JavaScript is required to be stable, so you can rely on it in all current browsers and Node.js. A handy trick follows: to sort by "last name, then first name", sort by the secondary key first and the primary key second.

7. Array.sort and the Default-String Trap

Now the pitfall that has caught almost every JavaScript developer. Try this:

console.log([10, 9, 1, 100, 25].sort());
// [ 1, 10, 100, 25, 9 ]

That is not sorted! The reason: with no argument, sort() converts every item to a string and compares the strings in dictionary order. The text "10" comes before "9" because "1" comes before "9". Numbers need a comparator:

console.log([10, 9, 1, 100, 25].sort((a, b) => a - b));
// [ 1, 9, 10, 25, 100 ]

console.log([10, 9, 1, 100, 25].sort((a, b) => b - a)); // descending
// [ 100, 25, 10, 9, 1 ]

The comparator (a, b) => a - b returns a negative number when a is smaller (so a goes first), positive when bigger, and zero on a tie. That is the contract from section 1.

More traps and rules:

• sort mutates the array and also returns it. const copy = [...arr].sort(...) avoids damaging the original. Newer runtimes also have toSorted(), which returns a copy.

• Uppercase sorts before lowercase in the default order, because of character codes:

  console.log(["banana", "apple", "Cherry"].sort());
  // [ 'Cherry', 'apple', 'banana' ]
  

  Copy

• For human-readable text, use localeCompare, which knows about accents and case:

  console.log(["banana", "apple", "Cherry"].sort((a, b) => a.localeCompare(b)));
  // [ 'apple', 'banana', 'Cherry' ]
  
  console.log(["é", "e", "z", "a"].sort());
  // [ 'a', 'e', 'z', 'é' ]  (é is after z by character code)
  
  console.log(["é", "e", "z", "a"].sort((a, b) => a.localeCompare(b)));
  // [ 'a', 'e', 'é', 'z' ]
  

  Copy

• undefined values are always moved to the end without being passed to your comparator.

• Do not write (a, b) => a > b. A comparator that returns a boolean gives true or false, which become 1 and 0: it never says "a comes first". Results are unreliable, depending on the engine.

• A subtraction comparator can break for huge values or NaN. a - b is fine for normal numbers. For values near Number.MAX_SAFE_INTEGER or when NaN might appear, use explicit comparisons.

Sorting objects by a field, and then by a second field as a tie-breaker:

const products = [
  { name: "Mouse", price: 25, stock: 4 },
  { name: "Cable", price: 5, stock: 40 },
  { name: "Hub", price: 25, stock: 12 },
];

products.sort((a, b) => a.price - b.price || b.stock - a.stock);

console.log(products.map((p) => p.name));
// [ 'Cable', 'Hub', 'Mouse' ]

Read it as "by price ascending; if the price difference is 0 (which is falsy), fall through to stock descending". Under the hood, V8 uses TimSort, a hybrid of merge sort and insertion sort that is stable, O(n log n) in the worst case, and close to O(n) on data that is already mostly ordered. For real work, use the built-in.

8. Counting Sort and the O(n log n) Limit

Can we ever beat O(n log n)? For sorts that work by comparing items, no: it is a proven lower bound. With n items there are n! possible orderings, and each comparison only answers yes or no, which gives at most 1 bit. You need about log₂(n!) comparisons, which is roughly n log n.

The way out is to not compare. If the values are small whole numbers in a known range, you can count them. Counting sort:

1. Make an array counts with one slot per possible value.
2. For each number, add 1 to its slot.
3. Walk the slots in order and write each value out as many times as it was counted.

function countingSort(nums: number[], max: number): number[] {
  const counts = new Array<number>(max + 1).fill(0);
  for (const n of nums) counts[n]++;

  const out: number[] = [];
  for (let value = 0; value <= max; value++) {
    for (let k = 0; k < counts[value]; k++) out.push(value);
  }
  return out;
}

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

This runs in O(n + k), where k is the range of values (here max). It is excellent for exam scores from 0 to 100, ages, star ratings, or the digits inside radix sort. It is a poor choice when the range is huge (sorting a few user IDs up to a billion would need a billion slots) or when values are not whole non-negative numbers. Radix sort and bucket sort are cousins of the same idea.

9. Benchmark

Let us see the Big-O gaps for real. Save this as bench-sort.ts in algolab, after finishing the recipe in the next section:

import {
  bubbleSort,
  insertionSort,
  mergeSort,
  quickSort,
  isSorted,
} from "./src/sorting.ts";

function randomNumbers(n: number): number[] {
  return Array.from({ length: n }, () => Math.floor(Math.random() * 1_000_000));
}

const algorithms: Record<string, (a: number[]) => number[]> = {
  bubble: (a) => bubbleSort(a),
  insertion: (a) => insertionSort(a),
  merge: (a) => mergeSort(a),
  quick: (a) => quickSort(a),
  "Array.sort": (a) => [...a].sort((x, y) => x - y),
};

for (const n of [2_000, 20_000]) {
  const data = randomNumbers(n);
  for (const [name, sort] of Object.entries(algorithms)) {
    const start = performance.now();
    const result = sort(data);
    const ms = performance.now() - start;
    console.log(`n=${n} ${name.padEnd(10)} ${ms.toFixed(1)} ms`,
      isSorted(result) ? "" : "NOT SORTED");
  }
}

npx tsx bench-sort.ts

One run on a laptop printed these times (yours will differ, but the shape should not):

Look at what happens when n grows 10 times. The quadratic sorts become about 70 to 80 times slower (close to the 100 times that n² predicts, with noise), while merge sort grows about 3 or 4 times, roughly as n log n predicts. At 20,000 items bubble sort is already more than 100 times slower than merge sort, and at a million items it would run for minutes.

The tiny timings at n = 2,000 are mostly noise, JIT warm-up included, so only trust big differences. Run each case a few times before drawing conclusions.

10. Recipe: sorting.ts for algolab

Create src/sorting.ts with every algorithm from this chapter:

export type Compare<T> = (a: T, b: T) => number;

const byDefault = <T>(a: T, b: T): number => (a < b ? -1 : a > b ? 1 : 0);

export function bubbleSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  const a = [...items];
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let i = 0; i < a.length - 1 - pass; i++) {
      if (compare(a[i], a[i + 1]) > 0) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return a;
}

export function insertionSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  const a = [...items];
  for (let i = 1; i < a.length; i++) {
    const current = a[i];
    let j = i - 1;
    while (j >= 0 && compare(a[j], current) > 0) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = current;
  }
  return a;
}

export function mergeSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  if (items.length <= 1) return [...items];
  const mid = Math.floor(items.length / 2);
  const left = mergeSort(items.slice(0, mid), compare);
  const right = mergeSort(items.slice(mid), compare);
  return merge(left, right, compare);
}

function merge<T>(left: T[], right: T[], compare: Compare<T>): T[] {
  const out: T[] = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (compare(left[i], right[j]) <= 0) out.push(left[i++]);
    else out.push(right[j++]);
  }
  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);
  return out;
}

export function quickSort<T>(items: T[], compare: Compare<T> = byDefault): T[] {
  const a = [...items];
  sortRange(a, 0, a.length - 1, compare);
  return a;
}

function sortRange<T>(a: T[], lo: number, hi: number, compare: Compare<T>): void {
  while (lo < hi) {
    const p = partition(a, lo, hi, compare);
    if (p - lo < hi - p) {
      sortRange(a, lo, p - 1, compare);
      lo = p + 1;
    } else {
      sortRange(a, p + 1, hi, compare);
      hi = p - 1;
    }
  }
}

function partition<T>(a: T[], lo: number, hi: number, compare: Compare<T>): number {
  const r = lo + Math.floor(Math.random() * (hi - lo + 1));
  [a[r], a[hi]] = [a[hi], a[r]];
  const pivot = a[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (compare(a[j], pivot) < 0) {
      [a[i], a[j]] = [a[j], a[i]];
      i++;
    }
  }
  [a[i], a[hi]] = [a[hi], a[i]];
  return i;
}

// Values must be whole numbers from 0 to max.
export function countingSort(nums: number[], max: number): number[] {
  const counts = new Array<number>(max + 1).fill(0);
  for (const n of nums) counts[n]++;
  const out: number[] = [];
  for (let value = 0; value <= max; value++) {
    for (let k = 0; k < counts[value]; k++) out.push(value);
  }
  return out;
}

export function isSorted<T>(items: T[], compare: Compare<T> = byDefault): boolean {
  for (let i = 1; i < items.length; i++) {
    if (compare(items[i - 1], items[i]) > 0) return false;
  }
  return true;
}

Now the tests in src/sorting.test.ts. One loop runs every algorithm against the same cases, and a second test compares them with the built-in sort on random data:

import { test } from "node:test";
import assert from "node:assert/strict";
import {
  bubbleSort,
  insertionSort,
  mergeSort,
  quickSort,
  countingSort,
  isSorted,
} from "./sorting.ts";

const sorts = { bubbleSort, insertionSort, mergeSort, quickSort };

for (const [name, sort] of Object.entries(sorts)) {
  test(`${name} sorts the usual cases`, () => {
    assert.deepEqual(sort([]), []);
    assert.deepEqual(sort([1]), [1]);
    assert.deepEqual(sort([5, 2, 9, 1, 5, 6]), [1, 2, 5, 5, 6, 9]);
    assert.deepEqual(sort([3, 2, 1]), [1, 2, 3]);
    assert.deepEqual(sort([1, 2, 3]), [1, 2, 3]);
    assert.deepEqual(sort([7, 7, 7]), [7, 7, 7]);
  });

  test(`${name} does not change its input`, () => {
    const input = [3, 1, 2];
    sort(input);
    assert.deepEqual(input, [3, 1, 2]);
  });

  test(`${name} matches Array.sort on random data`, () => {
    for (let round = 0; round < 20; round++) {
      const data = Array.from({ length: 200 }, () =>
        Math.floor(Math.random() * 100),
      );
      const expected = [...data].sort((a, b) => a - b);
      assert.deepEqual(sort(data), expected);
    }
  });

  test(`${name} accepts a custom comparator`, () => {
    assert.deepEqual(sort([1, 3, 2], (a, b) => b - a), [3, 2, 1]);
  });
}

test("insertion sort and merge sort are stable", () => {
  const people = [
    { name: "A", age: 30 },
    { name: "B", age: 25 },
    { name: "C", age: 30 },
    { name: "D", age: 25 },
  ];
  const byAge = (x: { age: number }, y: { age: number }) => x.age - y.age;
  for (const sort of [insertionSort, mergeSort, bubbleSort]) {
    assert.equal(sort(people, byAge).map((p) => p.name).join(""), "BDAC");
  }
});

test("countingSort", () => {
  assert.deepEqual(countingSort([3, 1, 4, 1, 5, 2, 3], 5), [
    1, 1, 2, 3, 3, 4, 5,
  ]);
  assert.deepEqual(countingSort([], 5), []);
});

test("isSorted", () => {
  assert.equal(isSorted([1, 2, 2, 3]), true);
  assert.equal(isSorted([2, 1]), false);
  assert.equal(isSorted([]), true);
});

Add the export to src/index.ts:

export * from "./sorting.ts";

Run the tests:

npx tsx --test

The "matches Array.sort on random data" test is the same trick as in the last chapter. Trust the built-in as the oracle and compare against it over many random inputs. Because quickSort uses a random pivot, running it many times also exercises many different paths.

11. Try It Yourself

1. Predict the default. Without running it, what does [5, 25, 100, 1].sort() return? What about ["b", "B", "a", "A"].sort()? Then run both and fix each with a comparator.
2. Sort by two keys. Given a list of { name, score }, sort by score descending and break ties by name ascending. Do it with a single comparator using the || trick, and then again with two stable sorts (secondary key first).
3. Count the work. Add a counter to mergeSort and bubbleSort that counts how many times compare is called. For an array of 1,000 random numbers, how many comparisons does each make? How close is bubble sort to n² / 2 and merge sort to n log₂ n?
4. Fix quick sort for duplicates. Rewrite partition as a three-way partition that groups items into < pivot, === pivot, and > pivot (the "Dutch national flag" scheme), and recurse only on the first and last groups. Time it on 50,000 identical numbers before and after.
5. Merge sorted arrays (interview). Given two sorted arrays, return one sorted array in O(n + m). Then extend it: given k sorted arrays, merge them all. What data structure makes k lists easy? (Hint: it is a few chapters away: heaps.)
6. Sort colors (interview). An array contains only 0, 1, and 2. Sort it in place in a single pass and O(1) extra space, without calling sort. Compare it to counting sort: which uses less memory? This is exactly the three-way partition from exercise 4.

Sorting turns messy data into something you can search, merge, and group in a single pass. And the central lesson of the last two chapters is that a better algorithm beats a faster computer. Next we move from flat lists to data with a shape. In Trees and Binary Search Trees we meet the structure behind the DOM and the file system, and see how a tree gives us fast search and fast insertion at the same time.