bastianplsfix

← JavaScript + TypeScript

Ordering and sorting

The equality page asked whether two values are the same. Ordering asks which one comes first, and it answers with different rules. Two facts sit behind almost every ordering bug: < and > compare strings by code unit, which is not the same as alphabetically, and Array.prototype.sort without a comparator converts every element to text, so it sorts numbers wrongly and stays quiet about it. This page earns both, and then the tools that give the order you actually wanted.

Create programs/ordering-and-sorting.test.ts for this reference and keep it open. Start it with the assertion helpers used on this page:

import { assert, assertEquals, assertFalse } from "@std/assert";

Follow the page as you add and revise the runnable examples below that import.

< compares numbers, and strings by code unit

The four relational operators, <, >, <=, and >=, work on numbers and on strings:

Deno.test("< compares numbers, and strings by code unit", () => {
  assert(5 >= 2);
  assert(1 < 2);
  assert("apple" < "banana");
  assertFalse("banana" < "apple");
});
Check programs/ordering-and-sorting.test.ts
running 1 test from ./programs/ordering-and-sorting.test.ts
< compares numbers, and strings by code unit ... ok (0ms)

ok | 1 passed | 0 failed (1ms)

Numbers compare numerically, and strings compare character by character using each character's code unit, its numeric value. "apple" < "banana" is true here because a's code unit is below b's, which happens to agree with the alphabet. The agreement is a coincidence of lowercase English, and a later step, code-unit order is not alphabetical order, shows exactly where it breaks.

One more thing to carry in: these operators convert their operands by rules of their own. That is how null >= 0 ends up true while null == 0 is false, the mismatch measured on the nothing-twice page in converted to a number, the two disagree.

NaN refuses to be ordered at all

The equality page showed NaN failing to equal anything. Ordering treats it the same way:

Deno.test("NaN refuses to be ordered at all", () => {
  const missing = Number.NaN;
  assertFalse(missing < 1);
  assertFalse(missing > 1);
  assertFalse(missing <= 1);
  assertFalse(missing >= 1);
});
NaN refuses to be ordered at all ... ok (0ms)

All four comparisons are false. NaN is not less than, greater than, equal to, or even less-than-or-equal-to anything, including itself. The consequence for this page: a single NaN in a list gives a sort contradictory answers, so the sort produces garbage rather than an error. The numbers page's advice in arithmetic never throws applies doubled here: validate at the edges, and filter NaN out before sorting.

the default sort is wrong for numbers

Sort three numbers with no comparator. Predict the result, then save. (toSorted returns a new sorted array; its older sibling sort gets a step of its own, sort rearranges the array you gave it.)

Deno.test("the default sort is wrong for numbers", () => {
  assertEquals([1, 10, 2].toSorted(), [1, 2, 10]);
});
Check programs/ordering-and-sorting.test.ts
running 3 tests from ./programs/ordering-and-sorting.test.ts
< compares numbers, and strings by code unit ... ok (0ms)
NaN refuses to be ordered at all ... ok (0ms)
the default sort is wrong for numbers ... FAILED (8ms)

 ERRORS

the default sort is wrong for numbers => ./programs/ordering-and-sorting.test.ts:19:11
error: AssertionError: Values are not equal.

    [Diff] Actual / Expected

    [
      1,
-     10,
      2,
+     10,
    ]

 FAILURES

the default sort is wrong for numbers => ./programs/ordering-and-sorting.test.ts:19:11

FAILED | 2 passed | 1 failed (10ms)

error: Test failed

The sorted result is [1, 10, 2]: ten before two. Here is the chain.

  1. With no comparator, sort converts each element to a string, so it is comparing "1", "10", and "2".
  2. Strings compare code unit by code unit, from the first step of this page, and "10" precedes "2" because the character "1" precedes the character "2".
  3. [1, 10, 2] was therefore already "sorted" as text, and the array came back untouched.

That last point is the worst possible outcome: it looks sorted. On a longer list the result is scrambled in a way that looks almost right, which is how this bug survives code review. Correct the prediction to [1, 10, 2], and add the fix, a comparator:

Deno.test("the default sort is wrong for numbers", () => {
  assertEquals([1, 10, 2].toSorted(), [1, 10, 2]);
  assertEquals([1, 10, 2].toSorted((a, b) => a - b), [1, 2, 10]);
});
the default sort is wrong for numbers ... ok (1ms)

A comparator receives two elements and answers with a number: negative if the first argument comes first, positive if the second does, and zero if the order between them does not matter. a - b produces all three answers at once for numbers, which is why it is the idiom.

a comparator must return a number

The comparator contract invites a mistake that reads perfectly naturally. "The first one comes first when it is smaller" suggests writing a comparison, so write one and save:

Deno.test("a comparator must return a number", () => {
  const numbers = [5, 1, 4, 2, 3];
  assertEquals(numbers.toSorted((a, b) => a > b), [1, 2, 3, 4, 5]);
});
Check programs/ordering-and-sorting.test.ts
TS2345 [ERROR]: Argument of type '(a: number, b: number) => boolean' is not assignable to parameter of type '(a: number, b: number) => number'.
  Type 'boolean' is not assignable to type 'number'.
    assertEquals(numbers.toSorted((a, b) => a > b), [1, 2, 3, 4, 5]);
                                  ~~~~~~~~~~~~~~~
    at file:///programs/ordering-and-sorting.test.ts:26:35

error: Type checking failed.

  info: The program failed type-checking, but it still might work correctly.
  hint: Re-run with --no-check to skip type-checking.

The checker refuses: a comparator must return a number, and a > b returns a boolean. To see why the rule matters, force the boolean through with a cast and watch what the sort does with it:

Deno.test("a comparator must return a number", () => {
  const numbers = [5, 1, 4, 2, 3];
  assertEquals(
    numbers.toSorted((a, b) => (a > b) as unknown as number),
    [5, 1, 4, 2, 3],
  );
  assertEquals(numbers.toSorted((a, b) => a - b), [1, 2, 3, 4, 5]);
});
a comparator must return a number ... ok (0ms)

The array came back in its original order, unsorted, with no error. Walk the chain.

  1. a > b produces true or false, and as numbers those coerce to 1 and 0.
  2. The contract reads 1 as "the second argument comes first" and 0 as "the order does not matter". There is no negative case, so this comparator never once says "the first argument comes first".
  3. A sort that is never told anything comes first leaves things where they are, silently.
  4. a - b covers the complete contract: it is negative when a < b, zero when the values are equal, and positive when a > b. Those three results put smaller numbers first, producing ascending order. The sort cares only about the sign, not the size of the result; use b - a when larger numbers should come first instead.

The checker caught this one before it ran, which is one more reason to keep comparators typed. For ascending numbers, the honest spelling stays a - b.

sort rearranges the array you gave it

toSorted has been doing the sorting so far. Its elder, sort, does the same comparison work with one large difference. Predict what amounts holds after the call:

Deno.test("sort rearranges the array you gave it", () => {
  const amounts = [3, 1, 2];
  const returned = amounts.sort((a, b) => a - b);
  assertEquals(returned === amounts, true);
  assertEquals(amounts, [1, 2, 3]);

  const safe = [3, 1, 2];
  assertEquals(safe.toSorted((a, b) => a - b), [1, 2, 3]);
  assertEquals(safe, [3, 1, 2]);
});
sort rearranges the array you gave it ... ok (0ms)

Two sorts, two fates for the original.

  1. amounts.sort(...) rearranged the array in place, and amounts is now [1, 2, 3]. The original order is gone.
  2. returned === amounts is true: the return value is the same array, not a copy. Writing const sorted = list.sort(...) creates two names for one reordered array, the aliasing from the values-and-references page's assigning an object copies the reference, and any code still holding list sees its order destroyed at a distance.
  3. safe.toSorted(...) produced a new sorted array and left safe exactly as written.

Prefer toSorted. toReversed, toSpliced, and with are its siblings, and each one replaces a method that used to mutate in place. When you do reach for sort, make it obvious that rearranging in place was the point.

sorting is stable

When the comparator calls two elements equal, something still has to decide their order in the result. Since ES2019 the specification decides it: they keep their original relative order. That guarantee is called stability, and it is observable:

Deno.test("sorting is stable", () => {
  const rows = [
    { key: "c", rank: 1 },
    { key: "b", rank: 2 },
    { key: "a", rank: 2 },
  ];
  const byRank = rows.toSorted((x, y) => x.rank - y.rank);
  assertEquals(byRank.map((row) => row.key), ["c", "b", "a"]);
});
sorting is stable ... ok (0ms)

Follow b and a.

  1. The comparator sorts by rank alone, and b and a share rank 2, so the comparator calls them equal.
  2. In the input, b came before a.
  3. In the output, b still comes before a. The tie was broken by the original order, as the specification requires.

Stability is what makes sorting by two keys work: sort by the weaker key first, then by the stronger one, and inside each group of the stronger key, the weaker order survives.

undefined is handled outside the comparator

One kind of element never reaches your comparator at all. Plant a witness, the seen array, and sort a list with an undefined in the middle:

Deno.test("undefined is handled outside the comparator", () => {
  const seen: string[] = [];
  const withHole: (number | undefined)[] = [3, undefined, 1];
  const sorted = withHole.toSorted((a, b) => {
    seen.push(`${a}/${b}`);
    return (a as number) - (b as number);
  });
  assertEquals(sorted, [1, 3, undefined]);
  assertEquals(seen, ["1/3"]);
});
undefined is handled outside the comparator ... ok (0ms)

Read the witness.

  1. sorted is [1, 3, undefined]: every undefined was moved to the end.
  2. seen holds one entry, "1/3". The comparator ran exactly once, for the two real numbers, and was never asked about the undefined.

The sort handles undefined itself, outside the comparator, by sending it to the back. That is convenient and worth knowing for both of its consequences: a comparator that would have crashed on undefined silently never sees one, and a comparator you wrote to place undefined somewhere else will not be obeyed.

code-unit order is not alphabetical order

The first step promised that code-unit order and the alphabet part ways. Here is where:

Deno.test("code-unit order is not alphabetical order", () => {
  assert("Z" < "a");
  assertEquals(
    ["apple", "Banana", "cherry"].toSorted(),
    ["Banana", "apple", "cherry"],
  );
  assertEquals(["é", "f", "z"].toSorted(), ["f", "z", "é"]);
});
code-unit order is not alphabetical order ... ok (0ms)

Two breaks, one cause.

  1. "Z" < "a" is true, because every capital letter's code unit sits below every lowercase one's. So the default sort files Banana before apple.
  2. Accented letters live above z in code-unit terms, so é sorts after z, at the end of the list.

Neither result is wrong as arithmetic, and both are wrong as alphabet. The comparison is answering "which numeric value is smaller?", and the reader is asking "which word comes first in the dictionary?". Those are different questions, and the next step shows why no single character-by-character rule could ever answer the second one.

languages disagree about alphabetical order

Alphabetical order is a property of a human language, not of the characters, and languages disagree about the same letters:

Deno.test("languages disagree about alphabetical order", () => {
  const letters = ["z", "ä", "a"];
  assertEquals(
    letters.toSorted(new Intl.Collator("sv").compare),
    ["a", "z", "ä"],
  );
  assertEquals(
    letters.toSorted(new Intl.Collator("de").compare),
    ["a", "ä", "z"],
  );
});
languages disagree about alphabetical order ... ok (4ms)

The same three letters, two correct answers.

  1. Swedish treats ä as a distinct letter at the end of its alphabet, so the Swedish collator puts it after z.
  2. German files ä with a, so the German collator puts it before z.

Both orders are right for their readers, and no character-by-character comparison could satisfy both. That is why the language ships the fast, dumb code-unit ordering as the default and puts the correct one behind an explicit request that names a locale.

a collator answers with human order

Intl.Collator is that request. Its compare method is a ready-made comparator you hand straight to a sort:

Deno.test("a collator answers with human order", () => {
  const compare = new Intl.Collator("en").compare;
  assertEquals(
    ["apple", "Banana", "cherry"].toSorted(compare),
    ["apple", "Banana", "cherry"],
  );

  assertEquals("a".localeCompare("B"), -1);
  assertFalse("a" < "B");

  assert("a".localeCompare("b") < 0);
  assert("b".localeCompare("a") > 0);
  assertEquals("a".localeCompare("a"), 0);
});
a collator answers with human order ... ok (0ms)

Three observations.

  1. The list that the default sort scrambled in code-unit order is not alphabetical order comes back in dictionary order: apple, Banana, cherry.
  2. The two mechanisms genuinely contradict each other. "a".localeCompare("B") is negative, so in human order a comes first, while "a" < "B" is false, so in code-unit order B comes first. A contradiction is the clearest possible evidence that they answer different questions.
  3. localeCompare answers negative, zero, or positive, exactly the comparator contract. Read the result as a sign and never as a distance: the specification promises the sign only, and comparing the result to -1, though it works today in Deno, is not something to build on.

String.prototype.localeCompare does the same job one comparison at a time. When sorting a list, build one collator and reuse it; that is both clearer and faster than a localeCompare call inside a loop.

numeric: true reads digits as numbers

Collators have one more job, and it is the reason to reach for one even in plain English. File names with numbers in them:

Deno.test("numeric: true reads digits as numbers", () => {
  const files = ["item10", "item2", "item1"];
  assertEquals(files.toSorted(), ["item1", "item10", "item2"]);
  assertEquals(
    files.toSorted(new Intl.Collator("en", { numeric: true }).compare),
    ["item1", "item2", "item10"],
  );
});
numeric: true reads digits as numbers ... ok (0ms)

The default sort puts item10 before item2, the same "1"-before-"2" code-unit fact as the default sort is wrong for numbers, now smuggled inside text. The collator built with numeric: true reads each run of digits as a number, so item2 comes before item10, which is what anyone looking at a file list expects. The other option worth knowing is sensitivity: "base", which ignores case and accents, and is how you build a case-insensitive sort without lowercasing your data first.

dates order, but are never equal

Dates end the page by splitting the two topics it started with: ordering works on them, equality does not.

Deno.test("dates order, but are never equal", () => {
  const early = new Date(0);
  const late = new Date(1000);
  assert(early < late);

  const d1 = new Date(0);
  const d2 = new Date(0);
  assertEquals(d1 === d2, false);
  assertEquals(d1.getTime() === d2.getTime(), true);

  const dates = [late, early];
  assertEquals(
    dates.toSorted((a, b) => a.getTime() - b.getTime()),
    [early, late],
  );
});
dates order, but are never equal ... ok (0ms)

Take the three parts in turn.

  1. early < late is true, because a relational operator converts a Date to its timestamp, the number hint from the conversion-and-coercion page's an object decides through valueOf and toString, and compares the numbers. Ordering dates works exactly as you would hope.
  2. d1 === d2 is false even though both name the same instant, because two dates are two objects, and the equality page's === on objects compares identity, not contents applies to them like any other object. Compare getTime() values when you mean sameness.
  3. The comparator spells the same conversion out: a.getTime() - b.getTime(). Writing a - b on dates would need a cast to get past the checker, and the explicit spelling says what the sort is actually comparing.

In practice