This story is about sorting arrays. I am telling it because sorting continues to surprise me with delightful bugs. Frustrating too, but also delightful.

First, some context. I’ve been working for years on a spreadsheet-database tool called Grist. Naturally, it lets users sort data. There are some complications, such as letting users sort by multiple columns. Also, a column may contain different types of values: for instance, mostly numbers but with some cells that are empty or that contain a string like “N/A” or “TBD”.

Normally, sorting happens in Javascript, on data that’s already in the browser. So this post is mostly about sorting in Javascript, although the most important points are not language-specific.

Default JavaScript Sort

We don’t need a complex example to start scratching our heads:

[10, 2, 'x'].sort()     // -> produces [ 10, 2, 'x' ]

This should not surprise you. We didn’t really say what we expect from mixing strings and numbers. Should 'a' come before 2 or after? Well, Javascript has a particular answer for us: it always sorts all items as strings. The result we see is alphabetically sorted, according to the order we’d get from converting each item to a string.

This is bad for a spreadsheet. We really expect 2 to come before 10.

Comparators

Luckily, Javascript gives us a way to fix this: pass in a comparator function that defines the sort order (1). Javascript expects this function to take two values, say, a and b, and return something negative when a < b, something positive when a > b, and 0 when a and b should be considered equivalent.

Most instructions for using sort() provide a helpful comparator function for sorting numbers:

function compareNumbers(a, b) {  return a - b;}

Indeed, it satisfies the requirements: the returned value is negative, positive, or zero in all the right cases. Let’s give it a try:

[10, 2, 'x' ].sort(compareNumbers)     // -> produces [ 2, 10, 'x' ]

Whew, you sigh! This looks correct, and was easy enough. Right? No, this would be too easy. Look at the result if we reverse two values in the original array:

[10, 'x' , 2].sort(compareNumbers)     // -> produces [ 10, 'x', 2 ]

This is not at all correct. It is even more upsetting that it’s even possible to get different answers.

Let’s think why this happened? Well, our comparator’s key operation is a - b. It makes sense for numbers, but not for the string 'x'. In fact, when comparing a number to a string, it returns NaN. Maybe that’s the problem. We were told to return positive, negative, or 0, not NaN.

Let’s fix our comparator function. Here is a versatile one:

function nativeCompare(a, b) {
  return (a < b ? -1 : (a > b ? 1 : 0));
}

In fact, it’s used a lot in Grist. It’s perfectly valid to compare 'x' < 2, there is no exception, and we always return a valid comparator value: never NaN. This one has got to work. Right?

[10, 2, 'x'].sort(nativeCompare)     // -> [ 2, 10, 'x' ]
[10, 'x', 2].sort(nativeCompare)     // -> [ 10, 'x', 2 ]

No, don’t tell me. The same exact terrible result as last time.

Transitivity

If you read far enough in the documentation of sort on MDN, you’ll find some more requirements that the comparator function needs to fulfill. Let’s see how our nativeCompare does on these requirements:

• It is pure: no side-effects of calling it.
• It is stable: it returns the same result for the same inputs.
• It is reflexive: it returns 0 when called with two of the same value (certainly for the values in our example).
• Is it anti-symmetric? Calling it for (a, b) or (b, a) should produce opposite signs. We should check.
• Is it transitive? If a < b and b < c, does it guarantee a < c? We should check.

These form the definition of something called a strict weak order (2). All that means is that “the order makes sense”. The fact that it’s not an obvious thing is what makes sorting bugs fun (and frustrating).

Our nativeCompare function really just repackages the behavior of the standard Javascript “less-than” and “greater-than” operators. Do those define an order that makes sense?

These operators are described in great detail here: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Less_than. Good luck figuring out what to expect. To save you some work, no, they do not define an order that “makes sense”. That’s because:

  1 < "2"  // true
"2" < "a"  // true
  1 < "a"  // false; broken transitivity!

Or with the values from our example:

  2 < 'x'  // false
'x' < 10   // false
  2 < 10   // true

This is a fail. By the standard of “makes sense”, the first two say that 2 >= 'x' and 'x' >= 10, and the third says 2 < 10, the opposite of what transitivity should give us.

Translating it to nativeCompare makes this a bit more precise:

nativeCompare(2, 'x')    // 0 (they are "equivalent")
nativeCompare('x', 10)   // 0 (they are "equivalent")
nativeCompare(2, 10)     // -1 (doh!)

This is a fail of transitivity.

But why is sort so fickle?

At this point, maybe it’s good to step back and say: transitivity-shmansitivity. All the operations are clearly correct for numbers. If we throw a string into the mix, we don’t really care if it ends up at the start or at the end. But why does it affect the relative order of the numbers? And why the inconsistency?

To answer that, we need to remember the sorting algorithms. That’s a lovely topic. I remember learning them in AP Computer Science in high school, and in algorithms class in college. These days, there is little need to know them: every modern language has an efficient sorting function or method readily available. But there is satisfaction in understanding them, because they are beautiful gems of insight. (3)

What’s worth remembering is that these are algorithms based on comparisons. They are fast because they minimize the number of comparisons. The efficient algorithms (including all the built-in implementations) make O(N log N) comparisons. This means that are optimally economical with comparisons.

Why does it matter? Because if the algorithm has already noticed that 2 is “equivalent” to 'x', and that 'x' is “equivalent” to 10, then it’s not going to compare 2 and 10 at all. Transitivity, remember? It already knows that 2 is “equivalent” to 10, without making the direct comparison.

Think of binary search for a simpler example: you start by comparing a value to one in the middle of a sorted array. This single comparison determines which half to limit the rest of the search to. You’ll never compare your value to anything in the other half. You don’t have to because of transitivity.

In short, with sorting, each comparison affects the result. So even a single violation of transitivity means that all bets are off. You will (guaranteed) find cases when your sort result is wrong.

“I will have order!”

The only way to fix it is to fix transitivity and anti-symmetry.

The basic idea is this:

function typedCompare(a, b) {
   return nativeCompare(typeof a, typeof b) || nativeCompare(a, b);
}

The || operator is a shorthand for saying: return the value on the left, but when it’s 0, then return the one on the right. The left part compares types (e.g. typeof 2 is "number"). If they are not equal, they determine the order of the values. So all numbers come before all strings (because "number" < "string"). When types are equal, then we compare the values themselves. Comparisons actually are consistent when applied only to strings. They are also consistent when applied only to normal numbers (not NaN or Infinity though). So this solution will in fact work for any mix of strings and normal numbers:

[10, 2, 'x'].sort(typedCompare)     // -> [ 2, 10, 'x' ]
[10, 'x', 2].sort(typedCompare)     // -> [ 2, 10, 'x' ]

Grist has to deal with other values, like arrays, and with other sort options, like ascending / descending, “natural sort”, and “empty values last” option. Grist is open-source so you can find all this fancy logic written in code here: https://github.com/gristlabs/grist-core/blob/main/app/common/SortFunc.ts.

OK, done yet?

When I said sorting continues to surprise me, I meant it.

The other day Grist had a fix landed for another sorting bug. For sorting empty values last, it had the following comparator function (simplified a bit for clarity):

function emptyCompareBad(a, b) {
  if (isEmpty(a)) {
    return 1;
  }
  if (isEmpty(b)) {
    return -1;
  }
  return 0;
}

The idea is straightforward: if a is empty, we compare a as “greater” than b, to sort after it (right?). Otherwise, we look at b. If that’s empty, we compare a as “less” than b. Otherwise, they are equivalent, as far as their emptiness is concerned.

No, in fact, this code was buggy. Here’s the fixed version. See if you can tell when it’s different:

function emptyCompareGood(a, b) {
  return nativeCompare(isEmpty(a), isEmpty(b));
}

// Recall what nativeCompare() is:
function nativeCompare(a, b) {
  return (a < b ? -1 : (a > b ? 1 : 0));
}

Are these versions equivalent? Sometimes yes, but not if both a and b are empty. In that case, the comparator should return 0 to indicate equivalence, but the bad version was returning 1. Does that break transitivity? No, actually (at least I haven’t found that), but it breaks the reflexive and anti-symmetric properties. Ultimately, the bug showed up in combination with other comparators.

Sorting in Grist is not perfect in other ways either. For instance, the values NaN and Infinity have the type 'number' but don’t get checked specially. The only reason that’s not a visible bug in Grist is that these are rarely used and not really supported as cell values. But if you do manage to include them in a Grist document (e.g. as formula return values), you can easily recreate a sorting bug like the ones covered in this post.

In conclusion

Sorting in Javascript requires a suitable comparator. It is science, not art. You have to pay attention to the types you need to support. My recommendation is to stitch the comparator out of simpler comparators that you can have confidence in: the first one to return a non-zero value should win.

If you make a mistake, it virtually guarantees that some arrays will sort incorrectly.

All this is not actually specific to Javascript. It’s a general observation of sorting. If your values are a single type, then there is probably a suitable comparator you can already use. When you have to create a comparator of your own, all these lessons apply.

---

(1) There are several equivalent ways to define a sort order: C++ standard library sort favors a function like “less than” (which return true or false), while Javascript and Python favor “comparator” (which returns negative, positive, or 0 to indicate “less-than”, “greater-than”, or “equivalent”).

(2) I’ll link to Wikipedia article https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings but it looks painful to read even for an enthusiastic theoretical math major.

(3) The value in understanding algorithms is similar to the value in understanding the Pythagorean Theorem (and why it’s true), or understanding why we have seasons on this Earth. Not necessary, but satisfying.