Sorting algorithms

The problem: an order report in the wrong order

The finance team at an online shop wants a daily report: every order, grouped by date, and within each date the largest orders first, so they can check the big ones before the bank closes. You have the orders as an array. The first attempt sorts the amounts and gets nonsense:

const amounts = [25000, 3500, 100, 1200000, 99000, 750];

const sorted = amounts.sort();
console.log(sorted.join(", "));
console.log("same array as before?", sorted === amounts);

100, 1200000, 25000, 3500, 750, 99000
same array as before? true

Two surprises. First, ₦1,200,000 sits between ₦100 and ₦25,000. With no arguments, sort turns every item into a string and orders the strings character by character, the way a dictionary does. "1200000" comes before "25000" because "1" comes before "2". Second, sort did not make a new array: it rearranged the original and returned the same one. Any other code holding amounts now sees it in a different order.

Fixing the first surprise takes one line (you will see it next). But the report raises bigger questions that one line does not answer. How does a computer put a million orders in order? Why are some ways of doing it a thousand times slower than others? Why does sorting by amount and then by date sometimes keep the amounts in order within each day, and sometimes scramble them? This lesson answers those by building the classic sorting algorithms yourself, counting the work each one does, and then using what you learned to drive JavaScript's built-in sort properly.

A sorting algorithm takes a list of items and a rule for which item comes first, and returns the same items rearranged so that every item comes before or together with the one after it. The rule is the interesting part, so it comes first.

The comparator: the rule that defines the order

Every sort in this lesson, and JavaScript's own sort, learns the order from a comparator: a function compare(a, b) that returns

• a negative number when a should come before b,
• a positive number when a should come after b,
• zero when the two are equal for this order (either may come first).

For numbers, a - b does all three at once: it is negative exactly when a < b. b - a reverses the order. Strings cannot be subtracted, so compare them with < and >, or with localeCompare for human text.

const amounts = [25000, 3500, 100, 1200000, 99000, 750];

console.log("ascending: ", amounts.toSorted((a, b) => a - b).join(", "));
console.log("descending:", amounts.toSorted((a, b) => b - a).join(", "));

const products = ["rice 50kg", "Garri", "beans", "Yam flour"];
console.log("< and >:     ", products.toSorted((a, b) => (a < b ? -1 : a > b ? 1 : 0)).join(" | "));
console.log("localeCompare:", products.toSorted((a, b) => a.localeCompare(b)).join(" | "));

console.log("boolean comparator:", amounts.toSorted((a, b) => a > b).join(", "));

ascending:  100, 750, 3500, 25000, 99000, 1200000
descending: 1200000, 99000, 25000, 3500, 750, 100
< and >:      Garri | Yam flour | beans | rice 50kg
localeCompare: beans | Garri | rice 50kg | Yam flour
boolean comparator: 25000, 3500, 100, 1200000, 99000, 750

toSorted (added in ES2023) sorts a copy and leaves the original alone, which is what you want most of the time. Notice three things:

• With < on strings, every capital letter comes before every lower-case letter, because the comparison uses character codes. localeCompare orders them the way a person expects.
• The last line is a very common bug. (a, b) => a > b returns true or false, which become 1 and 0. It never returns a negative number, so the sort is never told that anything comes before anything else. The result depends on the engine's internal algorithm; here the array came back unchanged, with no error. A comparator must be able to return all three signs.
• Sorting never changes the items themselves, only their positions. That is why you can sort order objects and still have the same order objects afterwards.

A comparator also has to be consistent: if a comes before b and b before c, then a must come before c, and it must give the same answer every time for the same pair. A comparator that uses Math.random() or reads a value that changes during the sort breaks this, and the result is some arbitrary arrangement, not a shuffle and not an error.

Counting the work

To compare algorithms fairly you need a measure that does not change from run to run. Timings do: they depend on the machine, on what else is running, and on the JIT compiler warming up (Big O and complexity explains why). This lesson counts comparisons (calls to the comparator) and writes (times a value is stored into the array). Both are exact and repeatable, and for a comparison sort the number of comparisons is the dominant cost.

All the sorts share a few helpers: a seeded random number generator, so "random" data is the same on every run, and a fresh counter object.

export function makeRandom(seed) {
  return () => (seed = (seed * 16807) % 2147483647) / 2147483647;
}

export function randomInts(n, max, seed = 1) {
  const random = makeRandom(seed);
  return Array.from({ length: n }, () => Math.floor(random() * max));
}

export function newStats() {
  return { comparisons: 0, writes: 0 };
}

export const ascending = (a, b) => a - b;

Every sort takes (input, compare, stats), copies the input first so the caller's array is never changed, and returns the sorted copy. That is the same contract as toSorted.

Bubble sort

The simplest idea: walk along the array comparing neighbours, and swap any pair that is in the wrong order. After one full pass the largest item has been carried all the way to the end, like a bubble rising. The next pass can stop one place earlier. If a pass makes no swaps at all, the array is sorted and you can stop.

pass 1:  [5 1 4 2]  ->  [1 5 4 2]  ->  [1 4 5 2]  ->  [1 4 2 5]   5 is in place
pass 2:  [1 4 2 | 5]  ->  [1 4 2]  ->  [1 2 4]                  4 is in place
pass 3:  [1 2 | 4 5]  ->  no swaps: stop

import { newStats } from "./tools.js";

export function bubbleSort(input, compare, stats = newStats()) {
  const a = [...input];
  for (let end = a.length - 1; end > 0; end--) {
    let swapped = false;
    for (let i = 0; i < end; i++) {
      stats.comparisons++;
      if (compare(a[i], a[i + 1]) > 0) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        stats.writes += 2;
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return a;
}

import { bubbleSort } from "./bubble.js";
import { ascending, newStats, randomInts } from "./tools.js";

console.log(bubbleSort([25000, 3500, 100, 1200000, 99000, 750], ascending).join(", "));

for (const n of [100, 1000]) {
  const random = newStats();
  bubbleSort(randomInts(n, 100000), ascending, random);
  const sorted = newStats();
  bubbleSort(Array.from({ length: n }, (_, i) => i), ascending, sorted);
  console.log(`n=${n}: random ${random.comparisons} comparisons, already sorted ${sorted.comparisons}`);
}

100, 750, 3500, 25000, 99000, 1200000
n=100: random 4779 comparisons, already sorted 99
n=1000: random 498225 comparisons, already sorted 999

On random data, ten times more items cost about a hundred times more comparisons: O(n²). Pass one makes n − 1 comparisons, pass two n − 2, and so on, which adds up to n(n − 1)/2. On data that is already sorted, the first pass makes no swaps and the swapped flag stops it after n − 1 comparisons: O(n) in the best case. Without that flag, bubble sort would do the full n²/2 even on sorted data.

Bubble sort is worth knowing because it is the easiest sort to get right and to reason about, not because you should use it. Its swaps only ever exchange neighbours, which makes it the slowest of the simple sorts in practice.

Selection sort

Selection sort works the way you might sort cards on a table: find the smallest card, put it first; find the smallest of the rest, put it second; and so on. Each step selects the minimum of the unsorted part and swaps it into place.

import { newStats } from "./tools.js";

export function selectionSort(input, compare, stats = newStats()) {
  const a = [...input];
  for (let i = 0; i < a.length - 1; i++) {
    let min = i;
    for (let j = i + 1; j < a.length; j++) {
      stats.comparisons++;
      if (compare(a[j], a[min]) < 0) min = j;
    }
    if (min !== i) {
      [a[i], a[min]] = [a[min], a[i]];
      stats.writes += 2;
    }
  }
  return a;
}

import { bubbleSort } from "./bubble.js";
import { selectionSort } from "./selection.js";
import { ascending, newStats, randomInts } from "./tools.js";

const n = 1000;
const inputs = {
  random: randomInts(n, 100000),
  sorted: Array.from({ length: n }, (_, i) => i),
};
for (const [label, data] of Object.entries(inputs)) {
  const s = newStats();
  selectionSort(data, ascending, s);
  const b = newStats();
  bubbleSort(data, ascending, b);
  console.log(`${label}: selection ${s.comparisons} comparisons / ${s.writes} writes, bubble ${b.comparisons} / ${b.writes}`);
}

random: selection 499500 comparisons / 1976 writes, bubble 498225 / 497286
sorted: selection 499500 comparisons / 0 writes, bubble 999 / 0

Selection sort always makes exactly n(n − 1)/2 comparisons, even when the input is already sorted: it cannot know that the rest is sorted without looking at all of it. It is Θ(n²) in every case. Its one strength is writes: at most one swap per position, so at most 2(n − 1) writes, against hundreds of thousands for bubble sort. When writing is far more expensive than comparing (moving heavy records, writing to flash memory that wears out), that can matter. Usually it does not.

Selection sort has a hidden weakness that you will see in the section on stability: the long-distance swap can jump an item over another item that is equal to it.

Insertion sort and the leaderboard

Insertion sort is how most people sort a hand of cards: take the next card and slide it left past every card that is bigger, until it sits in the right place. The left part of the array is always sorted; each step inserts one more item into it.

import { newStats } from "./tools.js";

export function insertionSort(input, compare, stats = newStats()) {
  const a = [...input];
  for (let i = 1; i < a.length; i++) {
    const item = a[i];
    let j = i - 1;
    while (j >= 0 && (stats.comparisons++, compare(a[j], item) > 0)) {
      a[j + 1] = a[j];
      stats.writes++;
      j--;
    }
    a[j + 1] = item;
    stats.writes++;
  }
  return a;
}

The inner loop stops at the first item that is not bigger, so an item that is already in place costs one comparison. How much work insertion sort does depends on how unsorted the input is. An inversion is a pair of items in the wrong order relative to each other; insertion sort shifts once per inversion. A sorted array has none (O(n) total), a reversed one has n(n − 1)/2 (O(n²)).

That makes insertion sort the right tool for data that is nearly sorted, which is common. The shop runs a loyalty leaderboard: customers ranked by points, highest first. After each purchase, one customer's points go up and the board must be re-sorted. Everyone else is still in order.

import { bubbleSort } from "./bubble.js";
import { insertionSort } from "./insertion.js";
import { selectionSort } from "./selection.js";
import { newStats } from "./tools.js";

const byPointsDesc = (a, b) => b.points - a.points;

const board = Array.from({ length: 1000 }, (_, i) => ({ name: `customer ${i + 1}`, points: 50000 - i * 40 }));
board[700] = { ...board[700], points: board[700].points + 9000 };

for (const [name, sort] of Object.entries({ insertionSort, bubbleSort, selectionSort })) {
  const stats = newStats();
  const ranked = sort(board, byPointsDesc, stats);
  const rank = ranked.findIndex((c) => c.name === "customer 701") + 1;
  console.log(`${name.padEnd(13)} customer 701 is now #${rank}, ${stats.comparisons} comparisons`);
}

insertionSort customer 701 is now #477, 1223 comparisons
bubbleSort    customer 701 is now #477, 199575 comparisons
selectionSort customer 701 is now #477, 499500 comparisons

Customer 701 climbed from place 701 to place 477. Insertion sort paid one comparison per customer plus one per place climbed: 999 + 224 = 1,223. Selection sort paid its full half million. Bubble sort did badly too, for a reason worth remembering: a pass carries a large item many places towards the end, but moves an item towards the front only one place. Customer 701 needed 224 passes of about a thousand comparisons each. Real libraries use insertion sort for small or nearly sorted pieces for exactly this reason, as you will see with Array.prototype.sort.

Bubble, selection and insertion sort are all O(n²) on random data, because each comparison can fix at most one inversion, and a random array has about n²/4 of them. To do better, an algorithm must fix many inversions with one move. The next two sorts do that by dividing the problem.

Merge sort

The shop has two branches, Lagos and Abuja. Each branch's till produces its orders in time order. Head office wants one list in time order. You do not need to sort anything: both lists are already sorted, so the earliest remaining order is always at the front of one of them. Compare the two fronts, take the earlier one, repeat. That is merging, and it takes one comparison per item: O(n) for two lists with n items in total.

import { newStats } from "./tools.js";

export function merge(left, right, compare, stats = newStats()) {
  const out = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    stats.comparisons++;
    if (compare(right[j], left[i]) < 0) out.push(right[j++]);
    else out.push(left[i++]);
  }
  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);
  stats.writes += out.length;
  return out;
}

export function mergeSort(input, compare, stats = newStats()) {
  if (input.length <= 1) return [...input];
  const mid = Math.floor(input.length / 2);
  const left = mergeSort(input.slice(0, mid), compare, stats);
  const right = mergeSort(input.slice(mid), compare, stats);
  return merge(left, right, compare, stats);
}

merge takes from the right only when the right item is strictly earlier. On a tie it takes from the left. Here it is on the two branches' streams:

import { merge } from "./merge.js";
import { newStats } from "./tools.js";

const lagos = [
  { time: "09:02", id: "L-101", naira: 12500 },
  { time: "10:15", id: "L-102", naira: 4800 },
  { time: "13:40", id: "L-103", naira: 99000 },
];
const abuja = [
  { time: "08:55", id: "A-201", naira: 3000 },
  { time: "10:15", id: "A-202", naira: 76000 },
  { time: "11:30", id: "A-203", naira: 15000 },
  { time: "16:05", id: "A-204", naira: 2200 },
];

const byTime = (a, b) => (a.time < b.time ? -1 : a.time > b.time ? 1 : 0);
const stats = newStats();
for (const order of merge(lagos, abuja, byTime, stats)) console.log(order.time, order.id);
console.log(`${lagos.length + abuja.length} orders, ${stats.comparisons} comparisons`);
console.log("empty branch:", merge([], abuja, byTime).map((o) => o.id).join(" "));

08:55 A-201
09:02 L-101
10:15 L-102
10:15 A-202
11:30 A-203
13:40 L-103
16:05 A-204
7 orders, 6 comparisons
empty branch: A-201 A-202 A-203 A-204

At 10:15 the Lagos order comes first because Lagos was the left input. Once Lagos ran out, the last Abuja order was copied without a comparison.

Merge sort turns merging into a full sort with recursion (Recursion): split the array in half, sort each half the same way, and merge the two sorted halves. The base case is a list of zero or one items, which is already sorted.

[38 27 43 3 9 82 10]
[38 27 43]        [3 9 82 10]          split
[38] [27 43]      [3 9] [82 10]        split
[38] [27] [43]    [3] [9] [82] [10]    single items are sorted
[38] [27 43]      [3 9] [10 82]        merge
[27 38 43]        [3 9 10 82]          merge
[3 9 10 27 38 43 82]                   merge

Halving can only happen about log₂ n times before the pieces have one item, so there are about log₂ n levels. On each level, all the merges together touch every item once: O(n) per level. That gives O(n log n) in total, and it holds for every input, sorted, reversed or random. The price is memory: merging needs a new array, so merge sort uses O(n) extra space. Divide and conquer takes this analysis further with recursion trees.

import { insertionSort } from "./insertion.js";
import { mergeSort } from "./merge.js";
import { ascending, newStats, randomInts } from "./tools.js";

for (const n of [1000, 10000, 100000]) {
  const data = randomInts(n, 1000000);
  const stats = newStats();
  const sorted = mergeSort(data, ascending, stats);
  const ok = sorted.every((v, i) => i === 0 || sorted[i - 1] <= v);
  console.log(`n=${n}: ${stats.comparisons} comparisons, n log2 n = ${Math.round(n * Math.log2(n))}, sorted ${ok}`);
}

const slow = newStats();
insertionSort(randomInts(10000, 1000000), ascending, slow);
console.log(`insertion sort, n=10000: ${slow.comparisons} comparisons`);

n=1000: 8688 comparisons, n log2 n = 9966, sorted true
n=10000: 120441 comparisons, n log2 n = 132877, sorted true
n=100000: 1536475 comparisons, n log2 n = 1660964, sorted true
insertion sort, n=10000: 24873964 comparisons

For 10,000 random items merge sort needs about 120,000 comparisons where insertion sort needs about 25 million. At 100,000 items the gap is 1.5 million against roughly 2.5 billion, which is the difference between an instant and a very long wait.

Quick sort

Merge sort does the easy split first (just cut in half) and the real work afterwards (merging). Quick sort does the opposite: it does the real work while splitting, so that nothing is left to do afterwards. It picks one item, the pivot, and partitions the array: everything smaller than the pivot to its left, everything else to its right. The pivot is now in its final place. Then it quick-sorts the left part and the right part.

The partition below is called the Lomuto scheme. It keeps a boundary store: everything before store is smaller than the pivot. It walks through the range, and each time it finds a smaller item it swaps it to the boundary and moves the boundary on. Finally it puts the pivot at the boundary. It sorts in place, with no second array.

import { newStats } from "./tools.js";

export function quickSort(input, compare, stats = newStats(), { pivot = "last", random = Math.random } = {}) {
  const a = [...input];
  const swap = (i, j) => {
    [a[i], a[j]] = [a[j], a[i]];
    stats.writes += 2;
  };
  stats.maxDepth = 0;

  function sort(lo, hi, depth) {
    if (lo >= hi) return;
    stats.maxDepth = Math.max(stats.maxDepth, depth);
    if (pivot === "random") swap(lo + Math.floor(random() * (hi - lo + 1)), hi);
    const p = a[hi];
    let store = lo;
    for (let i = lo; i < hi; i++) {
      stats.comparisons++;
      if (compare(a[i], p) < 0) swap(i, store++);
    }
    swap(store, hi);
    sort(lo, store - 1, depth + 1);
    sort(store + 1, hi, depth + 1);
  }

  sort(0, a.length - 1, 1);
  return a;
}

The pivot option chooses between the textbook choice (the last item of the range) and a random item. The random function can be passed in, so a test can make "random" repeatable. maxDepth records how deep the recursion went.

import { quickSort } from "./quick.js";
import { ascending, makeRandom, newStats, randomInts } from "./tools.js";

const n = 2000;
const inputs = {
  random: randomInts(n, 1000000),
  "already sorted": Array.from({ length: n }, (_, i) => i),
};

for (const [label, data] of Object.entries(inputs)) {
  for (const pivot of ["last", "random"]) {
    const stats = newStats();
    quickSort(data, ascending, stats, { pivot, random: makeRandom(42) });
    console.log(`${label.padEnd(14)} pivot=${pivot.padEnd(6)} ${String(stats.comparisons).padStart(7)} comparisons, depth ${stats.maxDepth}`);
  }
}

random         pivot=last     24686 comparisons, depth 22
random         pivot=random   26581 comparisons, depth 23
already sorted pivot=last   1999000 comparisons, depth 1999
already sorted pivot=random   25416 comparisons, depth 24

On random data quick sort is excellent: a little more than n log₂ n comparisons (2,000 × log₂ 2,000 is about 21,900), a recursion depth of a couple of dozen levels, and no extra array. On already sorted data with the last item as pivot, it collapses. The last item is the largest, so the partition puts everything on one side and nothing on the other; each level removes only one item. That is n levels, n²/2 comparisons: O(n²), as slow as bubble sort. The recursion is also 2,000 calls deep; with tens of thousands of sorted items it would overflow the call stack (Recursion shows that error).

Sorted input is not an exotic case. "Re-sort the orders, which are mostly sorted already" is one of the most common things a program does. A random pivot fixes it: no particular input is bad any more, only unlucky coin flips, and the chance of a bad run on a large array is vanishingly small. The expected cost is O(n log n) and the worst case O(n²) remains possible in theory.

Failure case: many equal keys

The warehouse sorts 2,000 order lines by status, and there are only three statuses. A random pivot does not help here:

import { quickSort } from "./quick.js";
import { makeRandom, newStats } from "./tools.js";

const statuses = ["delivered", "paid", "shipped"];
const random = makeRandom(9);
const lines = Array.from({ length: 2000 }, () => statuses[Math.floor(random() * 3)]);

const byStatus = (a, b) => (a < b ? -1 : a > b ? 1 : 0);
const stats = newStats();
quickSort(lines, byStatus, stats, { pivot: "random", random: makeRandom(42) });
console.log(`${stats.comparisons} comparisons, depth ${stats.maxDepth}`);

672994 comparisons, depth 671

After the first few partitions, every range contains only one status. The partition puts every item that is equal to the pivot on the right side, so a range of about 670 equal items shrinks by one per level, just like sorted input. The fix is a three-way partition: split the range into smaller, equal and larger, and recurse only into smaller and larger. Items equal to the pivot are finished in one pass.

import { newStats } from "./tools.js";

export function quickSort3(input, compare, stats = newStats(), random = Math.random) {
  const a = [...input];
  const swap = (i, j) => {
    [a[i], a[j]] = [a[j], a[i]];
    stats.writes += 2;
  };

  function sort(lo, hi) {
    if (lo >= hi) return;
    const p = a[lo + Math.floor(random() * (hi - lo + 1))];
    let lt = lo;
    let i = lo;
    let gt = hi;
    while (i <= gt) {
      stats.comparisons++;
      const c = compare(a[i], p);
      if (c < 0) swap(lt++, i++);
      else if (c > 0) swap(i, gt--);
      else i++;
    }
    sort(lo, lt - 1);
    sort(gt + 1, hi);
  }

  sort(0, a.length - 1);
  return a;
}

While it runs, a[lo..lt-1] holds smaller items, a[lt..i-1] equal ones, a[gt+1..hi] larger ones, and a[i..gt] is still unexamined. A larger item is swapped to the end without advancing i, because the item that comes back from the end has not been examined yet.

import { quickSort3 } from "./quick3.js";
import { makeRandom, newStats, randomInts } from "./tools.js";

const statuses = ["delivered", "paid", "shipped"];
const random = makeRandom(9);
const lines = Array.from({ length: 2000 }, () => statuses[Math.floor(random() * 3)]);
const byStatus = (a, b) => (a < b ? -1 : a > b ? 1 : 0);

const few = newStats();
const sorted = quickSort3(lines, byStatus, few, makeRandom(42));
console.log(`3 statuses: ${few.comparisons} comparisons, first ${sorted[0]}, last ${sorted.at(-1)}`);

const many = newStats();
quickSort3(randomInts(2000, 1000000), (a, b) => a - b, many, makeRandom(42));
console.log(`distinct numbers: ${many.comparisons} comparisons`);

3 statuses: 3993 comparisons, first delivered, last shipped
distinct numbers: 26563 comparisons

From about 670,000 comparisons down to a few thousand: with three distinct keys, three-way quick sort does roughly one pass per distinct value. On data with no duplicates it costs about the same as the two-way version.

Quick sort is not stable: the long-distance swaps in the partition can move an item past an equal one. Its extra space is the recursion stack, O(log n) on average. It is fast in practice because it scans memory in order and swaps in place, which suits the processor's cache.

All five side by side

Same inputs, same comparator, every algorithm. Four kinds of input: random numbers, already sorted, reversed, and "nearly sorted" (sorted with ten neighbouring pairs swapped, like the leaderboard).

import { bubbleSort } from "./bubble.js";
import { insertionSort } from "./insertion.js";
import { mergeSort } from "./merge.js";
import { quickSort } from "./quick.js";
import { selectionSort } from "./selection.js";
import { ascending, makeRandom, newStats, randomInts } from "./tools.js";

const n = 2000;
const nearly = Array.from({ length: n }, (_, i) => i);
const random = makeRandom(5);
for (let k = 0; k < 10; k++) {
  const i = Math.floor(random() * (n - 1));
  [nearly[i], nearly[i + 1]] = [nearly[i + 1], nearly[i]];
}
const inputs = {
  random: randomInts(n, 1000000),
  sorted: Array.from({ length: n }, (_, i) => i),
  reversed: Array.from({ length: n }, (_, i) => n - i),
  nearly,
};

const sorts = {
  bubble: bubbleSort,
  selection: selectionSort,
  insertion: insertionSort,
  merge: mergeSort,
  "quick (random pivot)": (data, cmp, stats) => quickSort(data, cmp, stats, { pivot: "random", random: makeRandom(42) }),
};

console.log("".padEnd(21) + Object.keys(inputs).map((k) => k.padStart(10)).join(""));
for (const [name, sort] of Object.entries(sorts)) {
  const cells = Object.values(inputs).map((data) => {
    const stats = newStats();
    sort(data, ascending, stats);
    return String(stats.comparisons).padStart(10);
  });
  console.log(name.padEnd(21) + cells.join(""));
}

                         random    sorted  reversed    nearly
bubble                  1997404      1999   1999000      3997
selection               1999000   1999000   1999000   1999000
insertion                988384      1999   1999000      2008
merge                     19388     10864     11088     10870
quick (random pivot)      26581     25416     25836     25595

Read the table by columns. On random data the two O(n log n) sorts need 19,000 to 27,000 comparisons and the three simple sorts one to two million. On sorted and nearly sorted data, bubble and insertion sort need only about n, and beat everything else. Merge sort is the only one that never has a bad column. Summarised:

Why not faster than n log n?

Every algorithm here learns about the order only by asking the comparator "which of these two comes first?". An array of n distinct items can be arranged in n! (n factorial: n × (n − 1) × … × 1) ways, and the sort must end up distinguishing all of them. Each comparison has two answers, so it can at best halve the number of arrangements still possible. Getting from n! possibilities down to one therefore takes at least log₂(n!) comparisons in the worst case, and log₂(n!) grows like n log₂ n. No comparison sort, however clever, can beat O(n log n) in the worst case. Merge sort and heap sort are optimal in this sense.

Sorts that do not compare, like counting sort, can be faster when the keys are small whole numbers: to order 100,000 product reviews by star rating (1 to 5), count how many reviews have each rating and write them out group by group, in O(n + k) for k possible keys. That trick only works when you know the keys in advance.

Stability: date first, then amount

Back to the finance report: orders by date, and within each date the largest amount first. A sort is stable if items that compare equal stay in the same order they had in the input. Stability lets you sort by several keys in steps: sort by the secondary key (amount, descending) first, then by the primary key (date) with a stable sort. Orders with the same date compare equal in the second sort, so they keep the amount order from the first. This is what happens when you click one column header in a spreadsheet and then another.

export const orders = [
  { id: 1001, date: "2026-09-02", naira: 4800 },
  { id: 1002, date: "2026-09-01", naira: 99000 },
  { id: 1003, date: "2026-09-02", naira: 250000 },
  { id: 1004, date: "2026-09-01", naira: 1200 },
  { id: 1005, date: "2026-09-03", naira: 15000 },
  { id: 1006, date: "2026-09-02", naira: 76000 },
  { id: 1007, date: "2026-09-01", naira: 35000 },
];

export const byDate = (a, b) => (a.date < b.date ? -1 : a.date > b.date ? 1 : 0);
export const byAmountDesc = (a, b) => b.naira - a.naira;

export function show(list) {
  return list.map((o) => `${o.date.slice(5)} #${o.id} ₦${o.naira}`).join("\n");
}

import { insertionSort } from "./insertion.js";
import { mergeSort } from "./merge.js";
import { byAmountDesc, byDate, orders, show } from "./orders.js";
import { selectionSort } from "./selection.js";

const byAmount = mergeSort(orders, byAmountDesc);

console.log("merge sort (stable):");
console.log(show(mergeSort(byAmount, byDate)));
console.log("insertion sort (stable) gives the same:", show(insertionSort(byAmount, byDate)) === show(mergeSort(byAmount, byDate)));
console.log("selection sort (not stable):");
console.log(show(selectionSort(byAmount, byDate)));

merge sort (stable):
09-01 #1002 ₦99000
09-01 #1007 ₦35000
09-01 #1004 ₦1200
09-02 #1003 ₦250000
09-02 #1006 ₦76000
09-02 #1001 ₦4800
09-03 #1005 ₦15000
insertion sort (stable) gives the same: true
selection sort (not stable):
09-01 #1002 ₦99000
09-01 #1007 ₦35000
09-01 #1004 ₦1200
09-02 #1003 ₦250000
09-02 #1001 ₦4800
09-02 #1006 ₦76000
09-03 #1005 ₦15000

With the stable sorts, each day's orders are still largest first. Selection sort gets the dates right, which is all its comparator asked for, but on 2 September it swapped ₦4,800 and ₦76,000: the long-distance swap moved order #1001 past #1006. Nothing failed; the report is simply wrong, and a finance clerk may not notice for weeks. The ISO date format YYYY-MM-DD is what makes < on the strings a correct date comparison: the most significant part comes first and every part has a fixed width.

One comparator with two keys

Sorting twice works, but it relies on stability and on the reader knowing the trick. Usually it is clearer to say exactly what you mean in one comparator: compare by date, and only if the dates are equal, compare by amount. Because 0 is falsy, || expresses "if the first comparison is a tie, use the next one":

import { byAmountDesc, byDate, orders, show } from "./orders.js";
import { selectionSort } from "./selection.js";

const byId = (a, b) => a.id - b.id;
const report = (a, b) => byDate(a, b) || byAmountDesc(a, b) || byId(a, b);

console.log(show(orders.toSorted(report)));
console.log("selection sort agrees:", show(selectionSort(orders, report)) === show(orders.toSorted(report)));

09-01 #1002 ₦99000
09-01 #1007 ₦35000
09-01 #1004 ₦1200
09-02 #1003 ₦250000
09-02 #1006 ₦76000
09-02 #1001 ₦4800
09-03 #1005 ₦15000
selection sort agrees: true

With a comparator that never returns 0 for two different orders (the order id is unique, so it is the final tie-breaker), stability stops mattering: every algorithm, stable or not, must produce exactly this output. That is a good habit whenever the order will be shown to people, saved, or used to split results into pages.

Array.prototype.sort in practice

You will rarely ship your own sort. JavaScript's sort and toSorted are fast and, since ES2019, guaranteed stable. V8 (the engine in Node.js and Chrome) uses TimSort, a hybrid of merge sort and insertion sort: it finds runs that are already in order, extends short runs with binary insertion sort, and merges the runs. That is why it is O(n) on sorted input and O(n log n) in the worst case, the best of both columns in your table. What remains your job is the comparator and knowing the method's behaviour.

let calls = 0;
const counted = (a, b) => (calls++, a - b);

const n = 10000;
const sortedAlready = Array.from({ length: n }, (_, i) => i);
sortedAlready.toSorted(counted);
console.log("sorted input, fewer than 2n comparisons:", calls < 2 * n);

calls = 0;
const shuffled = Array.from({ length: n }, (_, i) => (i * 7919) % n);
shuffled.toSorted(counted);
console.log("shuffled input, fewer than n log2 n comparisons:", calls < n * Math.log2(n));
console.log("shuffled input, fewer than n²/100 comparisons:", calls < (n * n) / 100);

const cart = [3500, undefined, 1200, undefined, 800];
console.log(cart.toSorted((a, b) => a - b));

const prices = [4500, 1200, 800];
const view = prices.toSorted((a, b) => a - b);
console.log(prices, view);

sorted input, fewer than 2n comparisons: true
shuffled input, fewer than n log2 n comparisons: true
shuffled input, fewer than n²/100 comparisons: true
[ 800, 1200, 3500, undefined, undefined ]
[ 4500, 1200, 800 ] [ 800, 1200, 4500 ]

• On sorted input TimSort needs only about n comparisons: it finds one run covering everything and has nothing to merge. On shuffled input it needs fewer than n log₂ n, far below the n² of the simple sorts. The example prints facts rather than exact counts, because the exact number of comparator calls differs between V8 versions (Node.js and Chrome can disagree by a few dozen), and a test should not depend on an engine's internals.
• undefined items are always moved to the end without calling your comparator. Holes in sparse arrays are too. Other odd values are not handled for you: a NaN amount makes a - b return NaN, which the sort treats like 0, and the result can be out of order around it. Validate the data before sorting it.
• toSorted leaves prices alone. Prefer it whenever the array came from somewhere else (a function argument, application state, a cached value). Use sort only on an array you just created yourself.

A reusable multi-key comparator

Report screens often let the user choose the sort columns. Instead of writing a new comparator each time, build one from a list of keys:

function by(...keys) {
  return (a, b) => {
    for (const { key, desc = false } of keys) {
      const x = a[key];
      const y = b[key];
      const c = typeof x === "string" ? x.localeCompare(y) : x - y;
      if (c !== 0) return desc ? -c : c;
    }
    return 0;
  };
}

const customers = [
  { name: "Tunde", city: "Lagos", points: 5400 },
  { name: "adaeze", city: "Abuja", points: 5400 },
  { name: "Chioma", city: "Lagos", points: 9100 },
  { name: "Bola", city: "Abuja", points: 2300 },
];

for (const c of customers.toSorted(by({ key: "points", desc: true }, { key: "name" }))) {
  console.log(c.points, c.name);
}
console.log(customers.toSorted(by({ key: "city" }, { key: "points", desc: true })).map((c) => c.name).join(", "));

9100 Chioma
5400 adaeze
5400 Tunde
2300 Bola
adaeze, Bola, Chioma, Tunde

Tunde and adaeze tie on points, so the name decides, and localeCompare puts the lower-case "adaeze" first where plain < would have put her last. For sorting many strings, new Intl.Collator("en").compare is a faster comparator that gives the same ordering as localeCompare, because the language rules are prepared once instead of on every call.

Testing a sort

A sort can be wrong in three ways: the output is not in order, the output is not the same items (something lost or duplicated), or equal items moved when they should not have. A handful of hand-picked cases catches the edge cases; a few hundred random arrays compared with a trusted reference (toSorted) catch the rest. Small value ranges create many duplicates, which is where sorting bugs hide.

import { bubbleSort } from "./bubble.js";
import { insertionSort } from "./insertion.js";
import { mergeSort } from "./merge.js";
import { quickSort } from "./quick.js";
import { quickSort3 } from "./quick3.js";
import { selectionSort } from "./selection.js";
import { makeRandom } from "./tools.js";

const sorts = {
  bubbleSort, selectionSort, insertionSort, mergeSort, quickSort,
  quickSort3: (data, cmp, stats) => quickSort3(data, cmp, stats, makeRandom(7)),
};
const stable = new Set(["bubbleSort", "insertionSort", "mergeSort"]);

const edgeCases = [[], [1], [2, 1], [3, 3, 3], [5, -2, 0, -2, 9], [1, 2, 3, 4], [4, 3, 2, 1]];
const random = makeRandom(2026);
const randomCases = Array.from({ length: 300 }, () =>
  Array.from({ length: Math.floor(random() * 40) }, () => Math.floor(random() * 6)),
);

for (const [name, sort] of Object.entries(sorts)) {
  let failures = 0;
  for (const input of [...edgeCases, ...randomCases]) {
    const before = input.join();
    const got = sort(input, (a, b) => a - b);
    if (got.join() !== input.toSorted((a, b) => a - b).join()) failures++;
    if (input.join() !== before) failures++;

    const tagged = input.map((value, index) => ({ value, index }));
    const out = sort(tagged, (a, b) => a.value - b.value);
    const keptOrder = out.every((x, i) => i === 0 || out[i - 1].value < x.value || out[i - 1].index < x.index);
    if (stable.has(name) && !keptOrder) failures++;
  }
  console.log(`${failures === 0 ? "PASS" : "FAIL"} ${name}: ${edgeCases.length + randomCases.length} inputs, ${failures} failures`);
}

PASS bubbleSort: 307 inputs, 0 failures
PASS selectionSort: 307 inputs, 0 failures
PASS insertionSort: 307 inputs, 0 failures
PASS mergeSort: 307 inputs, 0 failures
PASS quickSort: 307 inputs, 0 failures
PASS quickSort3: 307 inputs, 0 failures

Each input is checked three ways: against toSorted (order and contents together, since comparing the joined strings catches a lost or duplicated item), for mutation of the input, and, for the sorts that promise it, stability. The stability check tags every value with its original index; in a stable result, equal values must appear with increasing indexes. To see the test earn its keep, change < 0 to <= 0 in merge (take from the right on ties): the output is still sorted, and only the stability check fails.

Sorting in production

• Sort in the database when the data lives there. ORDER BY created_at DESC, id DESC with an index on those columns returns rows already in order, and the database can stop after the first page instead of sorting everything. Loading 100,000 rows into Node to sort them and show 20 wastes memory and time. SQL basics covers ORDER BY.
• Pages need a total order. If page 1 is "the first 20 orders by date" and many orders share a date, the database may break the ties differently on the next request, so an order appears on two pages or on none. Always end the sort with a unique key such as the id, exactly like the report comparator above.
• Money and dates. Compare amounts as integers (kobo, not floating-point naira) and dates as timestamps or ISO strings with the same time zone. Sorting "9/2/2026"-style strings orders them by day or month digit, not by date.
• Do not sort in a loop. Sorting a list on every request, or re-sorting after every insert, turns an O(n log n) job into O(n² log n). Keep the data sorted as it changes (insertion, a heap, or a database index), or sort once and cache the result.
• You only need the top 10? Do not sort a million items to keep ten. A size-k heap gives the top k in O(n log k) (Heaps), and Divide and conquer shows quickselect, which finds the k-th item in O(n) on average.
• Comparators run a lot. Sorting 100,000 items calls the comparator about 1.7 million times. Keep it cheap: no parsing dates, no database calls, no toLowerCase on every call. Compute a sort key once per item, sort by the key, and map back.
• Beware user-controlled sort fields. A ?sort= parameter must be checked against a list of allowed columns before it reaches a comparator or an SQL ORDER BY; SQL cannot take a column name as a bound parameter, so an unchecked one is an injection risk.

Practice

const players = [
  { name: "Kemi", points: 80, seconds: 410 },
  { name: "Ifeanyi", points: 95, seconds: 530 },
  { name: "Amaka", points: 80, seconds: 390 },
  { name: "Musa", points: 95, seconds: 530 },
  { name: "Dayo", points: 60, seconds: 300 },
];

const ranking = (a, b) => b.points - a.points || a.seconds - b.seconds || a.name.localeCompare(b.name);

players.toSorted(ranking).forEach((p, i) => console.log(`${i + 1}. ${p.name} ${p.points} pts ${p.seconds}s`));

1. Ifeanyi 95 pts 530s
2. Musa 95 pts 530s
3. Amaka 80 pts 390s
4. Kemi 80 pts 410s
5. Dayo 60 pts 300s

function mergeUnique(a, b) {
  const out = [];
  let i = 0;
  let j = 0;
  let comparisons = 0;
  const add = (id) => {
    if (out.at(-1) !== id) out.push(id);
  };
  while (i < a.length && j < b.length) {
    comparisons++;
    if (a[i] < b[j]) add(a[i++]);
    else if (b[j] < a[i]) add(b[j++]);
    else {
      add(a[i++]);
      j++;
    }
  }
  while (i < a.length) add(a[i++]);
  while (j < b.length) add(b[j++]);
  return { out, comparisons };
}

const lagos = [1001, 1003, 1004, 1008, 1010];
const abuja = [1002, 1003, 1008, 1009, 1011, 1012];
const { out, comparisons } = mergeUnique(lagos, abuja);
console.log(out.join(" "));
console.log(`${lagos.length + abuja.length} ids in, ${out.length} out, ${comparisons} comparisons`);
console.log(mergeUnique([], [5, 5, 6]).out.join(" "));

1001 1002 1003 1004 1008 1009 1010 1011 1012
11 ids in, 9 out, 7 comparisons
5 6

function quickSort(input, compare, pivot) {
  const a = [...input];
  let comparisons = 0;
  const swap = (i, j) => ([a[i], a[j]] = [a[j], a[i]]);

  function medianIndex(lo, hi) {
    const mid = Math.floor((lo + hi) / 2);
    const trio = [lo, mid, hi].sort((x, y) => compare(a[x], a[y]));
    return trio[1];
  }

  function sort(lo, hi) {
    if (lo >= hi) return;
    if (pivot === "median3") swap(medianIndex(lo, hi), hi);
    const p = a[hi];
    let store = lo;
    for (let i = lo; i < hi; i++) {
      comparisons++;
      if (compare(a[i], p) < 0) swap(i, store++);
    }
    swap(store, hi);
    sort(lo, store - 1);
    sort(store + 1, hi);
  }

  sort(0, a.length - 1);
  return { a, comparisons };
}

const n = 2000;
const inputs = {
  sorted: Array.from({ length: n }, (_, i) => i),
  reversed: Array.from({ length: n }, (_, i) => n - i),
};
for (const [label, data] of Object.entries(inputs)) {
  for (const pivot of ["last", "median3"]) {
    const { a, comparisons } = quickSort(data, (x, y) => x - y, pivot);
    const ok = a.every((v, i) => i === 0 || a[i - 1] <= v);
    console.log(`${label.padEnd(8)} ${pivot.padEnd(7)} ${comparisons} comparisons, sorted ${ok}`);
  }
}

sorted   last    1999000 comparisons, sorted true
sorted   median3 17964 comparisons, sorted true
reversed last    1999000 comparisons, sorted true
reversed median3 33670 comparisons, sorted true

Summary

• A comparator returns negative, zero or positive, and must be consistent. a - b for numbers, localeCompare or Intl.Collator for text. Without one, sort compares as strings. A comparator that returns booleans silently breaks the sort.
• Bubble, selection and insertion sort are O(n²) on random data. Insertion sort is O(n) on nearly sorted data and does one shift per inversion; selection sort always does n²/2 comparisons but very few writes.
• Merge sort splits in half, sorts both halves and merges them: O(n log n) always, O(n) extra space, stable because merge takes from the left on ties.
• Quick sort partitions around a pivot: O(n log n) on average and in place, but O(n²) with a fixed pivot on sorted data, and on many equal keys unless it uses a three-way partition. It is not stable.
• No comparison sort beats O(n log n) in the worst case. Count comparisons, not milliseconds, to compare algorithms.
• A stable sort keeps equal items in their input order. Either sort by the secondary key and then stably by the primary, or better, write one comparator with all keys and a unique tie-breaker.
• Array.prototype.sort is stable TimSort, sorts in place and returns the same array; toSorted returns a copy. undefined goes last; NaN breaks the order. Test sorts against toSorted on many small random arrays with duplicates, and check stability with tagged items.

Next: Divide and conquer takes the idea behind merge sort and quick sort, split the problem, solve the parts, combine, and uses it for quickselect, fast exponentiation and the recursion trees that tell you what a recursive algorithm costs.