Lessons · TypeScript · what sorting costs

What sorting costs, and what it buys

sort() costs about n log n and is stable in modern JavaScript, so items that compare equal keep the order they had. By default it sorts as TEXT, so numbers need a comparator.

Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.

What it is for

Sorting is often the cheap step that makes the real work easy: paying n log n once to turn a comparison of every pair into a single pass is one of the best trades in programming.

How to think about it

Before writing two nested loops, ask what order would give you. If sorted order makes the next thing you care about the very next item, sort first and walk once.

Worked example

console.log([10, 9, 100].sort().join(','));

10,100,9

console.log([10, 9, 100].sort((a, b) => a - b).join(','));

9,10,100

const scores = [['cy', 90], ['ada', 90], ['bo', 70]];

cy is before ada, and they tie.

scores.sort((x, y) => x[1] - y[1]);

Stable: the tie keeps its original order.

console.log(scores.map(s => s[0]).join(','));

bo,cy,ada

const readings = [41, 7, 40, 15, 8];

Find the two closest values.

readings.sort((a, b) => a - b);

In place; sort returns the same array.

let closest = Infinity;

for (let i = 1; i < readings.length; i++) closest = Math.min(closest, readings[i] - readings[i - 1]);

One pass, not every pair.

console.log(closest);

Your turn

Sort numbers by value, not as text.

values.sort((a, b) => );

The trap

[10, 9, 100].sort() gives 10, 100, 9, because the default comparator compares strings. It is the single most common sorting bug in JavaScript, and it looks right on one-digit data.

Practise what sorting costs on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.