Sorting in practice

The default comparator is a trap

JavaScript’s default sort converts everything to a string. That is not a quirk to work around occasionally — it silently produces wrong output on every array of numbers, and it is probably the most common bug in this entire course.

For text, localeCompare (or Intl.Collator, which is much faster in a loop) handles accents, case and language. Python’s sorted has no such trap: it compares the values themselves and refuses to compare types that do not make sense together.

[10, 9, 100, 1].sort()                 // [1, 10, 100, 9]  — compared as TEXT
[10, 9, 100, 1].sort((a, b) => a - b)  // [1, 9, 10, 100]

["b", "a"].sort()                      // fine for ASCII
["ä", "z", "a"].sort()                 // ["a", "z", "ä"] — not what any reader expects
["ä", "z", "a"].sort((a, b) => a.localeCompare(b))   // ["a", "ä", "z"]

A comparator has three rules

It must be consistent: if a < b and b < c then a < c, and compare(a, b) must always be the negative of compare(b, a). A comparator that returns true/false, or that uses Math.random(), breaks the sort — not by shuffling, but by producing arbitrary output or, in some engines, an exception.

Returning a boolean is the second classic bug: (a, b) => a > b returns true or false, which coerce to 1 and 0 — so "b comes first" is never expressed and the array comes back almost, but not quite, sorted.

compare(a, b) < 0    // a comes first
compare(a, b) > 0    // b comes first
compare(a, b) === 0  // they tie

Sort by a key, and by several

The || chain works because a tie returns 0, which is falsy, so the next comparison decides. It reads in the order a human would say it: "by score, then by name".

The alternative, used when the sort is stable, is to sort twice — least significant key first. Both are correct; the chain is clearer and does one pass.

rows.sort((a, b) => a.score - b.score);                       // one number
rows.sort((a, b) => b.score - a.score);                       // descending
rows.sort((a, b) => a.name.localeCompare(b.name));            // one string

rows.sort((a, b) =>
  b.score - a.score ||                                        // score, descending
  a.name.localeCompare(b.name));                              // then name, ascending

Decorate, sort, undecorate

A comparator is called O(n log n) times, so anything expensive inside it is multiplied by that. Computing the key once per item first — the Schwartzian transform — turns the cost from n log n key computations into n. Python builds this in as sorted(rows, key=...), which is why key= is always preferred there over cmp_to_key.

/* slow: normalise() runs about 2·n·log n times */
rows.sort((a, b) => normalise(a.name).localeCompare(normalise(b.name)));

/* fast: normalise() runs exactly n times */
const decorated = rows.map((row) => ({ key: normalise(row.name), row }));
decorated.sort((a, b) => a.key.localeCompare(b.key));
const sorted = decorated.map((d) => d.row);

What to reach for

And the rule under all of them: sorting is O(n log n), so if you only need the smallest item, Math.min is O(n) and sorting to find it is waste.