Sorting in JavaScript: Shouldn't Returning a Boolean Be Enough For a Comparison Function

Sorting in JavaScript: Shouldn't returning a boolean be enough for a comparison function?

TL;DR

I have always successfully sorted my arrays like this

No, you have not. And didn't notice it. Some quick counterexamples:

> [0,1,0].sort(function(a,b){ return a>b })
Array [0, 1, 0] // in Chrome, in Internet Exploder 11.
// Results may vary between sorting algorithm implementations
> [1,1,0,2].sort(function(a, b){ return a>b })
Array [0, 1, 2, 1] // in Opera 12.
Array [1, 1, 0, 2] // in Chrome 100, in Internet Exploder 11.
// Results will vary between sorting algorithm implementations

why?

Because your comparison function does return false (or 0, equivalently) even when b is larger than a. But 0 implies that the two elements are considered equal - and the sorting algorithm believes that.

In-Depth Explanation

Comparison functions in JavaScript

How do comparison functions work?

The Array::sort method can take an optional, custom comparison function as its argument. That function takes two arguments (commonly referred to as a and b) which it should compare, and is supposed to return a number

> 0 when a is considered larger than b and should be sorted after it
== 0 when a is considered equal to b and it doesn't matter which comes first
< 0 when a is considered smaller than b and should be sorted before it

If it does not return a number, the result will be cast to a number (which is handy for booleans). The returned number does not need to be exactly -1 or 0 or 1 (though it typically is).

Consistent ordering

To be consistent, the compare function would need to fulfill the equation

comp(a, b) == -1 * comp(b, a)
// or, if values other than -1, 0 and 1 are considered:
comp(a, b) * comp(b, a) <= 0

If that requirement is broken, the sort will behave undefined.

Citing the ES5.1 spec on sort (same thing in the ES6 spec):

If comparefn is […] not a consistent comparison function for the elements of this array, the behaviour of sort is implementation-defined.
A function comparefn is a consistent comparison function for a set of values S if all of the requirements below are met for all values a, b, and c (possibly the same value) in the set S: The notation a <CF b means comparefn(a,b) < 0; a =CF b means comparefn(a,b) = 0 (of either sign); and a >CF b means comparefn(a,b) > 0.
Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments. Furthermore, Type(v) is Number, and v is not NaN. Note that this implies that exactly one of a <CF b, a =CF b, and a >CF b will be true for a given pair of a and b.
Calling comparefn(a,b) does not modify the this object.
a =CF a (reflexivity)
If a =CF b, then b =CF a (symmetry)
If a =CF b and b =CF c, then a =CF c (transitivity of =CF)
If a <CF b and b <CF c, then a <CF c (transitivity of <CF)
If a >CF b and b >CF c, then a >CF c (transitivity of >CF)
NOTE: The above conditions are necessary and sufficient to ensure that comparefn divides the set S into equivalence classes and that these equivalence classes are totally ordered.

Uh, what does this mean? Why should I care?

A sorting algorithm needs to compare items of the array with each other. To do a good and efficient job, it must not need to compare each item to every other, but needs to be able to reason about their ordering. For that to work well, there are a few rules that a custom comparison function needs to abide. A trivial one is that an item a is equal to itself (compare(a, a) == 0) - that's the first item in the list above (reflexivity). Yes, this is a bit mathematical, but pays of well.

The most important one is transitivity. It says that when the algorithm has compared two values a and b, and also b with c, and has found out by applying the comparison function that e.g. a = b and b < c, then it can expect that a < c holds as well. This seems only logical, and is required for a well-defined, consistent ordering.

But your comparison function does fail this. Lets look at this example:

 function compare(a, b) { return Number(a > b); }
 compare(0, 2) == 0 // ah, 2 and 0 are equal
 compare(1, 0) == 1 // ah, 1 is larger than 0
 // let's conclude: 1 is also larger than 2

Ooops. And that is why a sorting algorithm can fail (in the spec, this is be "implementation-dependent behaviour" - i.e. unpredictable results) when it is invoked with a comparison function that is not consistent.

Why is the wrong solution so common?

Because in many other languages, there are sorting algorithms that don't expect a three-way comparison but merely a boolean smaller-than operator. C++ std::sort is a good example of that. It will simply be applied twice with swapped arguments if an equality needs to be determined. Admittedly, this can be more efficient and is less error-prone, but needs more calls to the comparison function if the operator cannot be inlined.

CounterExamples

I have tested my comparison function, and it works!

Only by sheer luck, if you tried some random example. Or because your test suite is flawed - incorrect and/or incomplete.

Here is the small script I used to find the above minimal counterexample:

function perms(n, i, arr, cb) {
// calls callback with all possible arrays of length n
    if (i >= n) return cb(arr);
    for (var j=0; j<n; j++) {
        arr[i] = j;
        perms(n, i+1, arr, cb);
    }
}
for (var i=2; ; i++) // infinite loop
    perms(i, 0, [], function(a) {
        if (    a.slice().sort(function(a,b){ return a>b }).toString()
             != a.slice().sort(function(a,b){ return a-b }).toString() )
            // you can also console.log() all of them, but remove the loop!
            throw a.toString();
    });

What comparison function is correct?

Use no comparison function at all, when you want a lexicographic sort. Items in the array will be stringified if necessary.

A generic comparison function that works like the relational operators can be implemented as

function(a, b) {
    if (a > b) return 1;
    if (a < b) return -1;
    /* else */ return 0;
}

With a few tricks, this can be minified to the equivalent function(a,b){return +(a>b)||-(a<b)}.

For numbers, you can simply return their difference, which abides all the laws above:

function(a, b) {
    return a - b; // but make sure only numbers are passed (to avoid NaN)
}

If you want to sort in reverse, just take the appropriate one and swap a with b.

If you want to sort composite types (objects etc), replace each a and each b with an access of the properties in question, or a method call or whatever you want to sort by.

Javascript sort function not sorting

Your compare function is returning a boolean. Array.sort() expects you to return a number.

If your compare functions returns a value < 0, 'a' will be placed before 'b'.

If your compare functions returns a value > 0, 'b' will be placed before 'a'.

If your compare functions returns 0, the order will remain as-is.

So, to sort by number of stars in descending order, you could do this:

this.topPlayers.sort((a, b) => b.stars - a.stars);

If 'a' has more stars than 'b', the return value will be negative, and 'a' will be sorted before 'b', and vice versa.

Array sort is not working correctly in JavaScript

Edited with additional info:

My apologies, but the shortest answer for this question is just:

function sort() {
    var ary = [2, 1, 0.4, 2, 0.4, 0.2, 1.5, 1, 1.1, 1.3, 1.2, 0.2, 0.4, 0.9];
    // use custom compare function that sorts numbers ascending
    alert(ary.sort(function(a, b) {
        return a - b;
    }));
}

sort();

How does JavaScript's sort (compareFunction) work?

It depends on the implementation. This actual implementation, looks like an insertion sort, with this amount of data (it could be different, like with Chrome, and the different implementation for less than 10 items or more items), is going from index zero to the end and if a swap has not taken place at the last two items, then it stops, otherwise it goes backwards to index zero.

Basically it tests and changes in this order

5   2   1 -10   8   original order
5   2
    2   1
        1 -10
          -10   8   swap
            8 -10
        1   8       swap
        8   1
    2   8           swap
    8   2
5   8               swap
8   5  2    1 -10   result

A more complex sorting shows better what is going on, with two greater values, which need to move to the other side of the array

8   9   1   2   3   4   original array
8   9
    9   1               swap
    1   9
8   1                   swap
1   8
        9   2           swap
        2   9
    8   2               swap
    2   8
1   2
            9   3       swap
            3   9
        8   3           swap
        3   8
    2   3
                9   4   swap
                4   9
            8   4       swap
            4   8
        3   4
1   2   3   4   8   9   result

Live example, does not work in all user agents (eg not in Edge, but in Chrome)

var array = [8, 9, 1, 2, 3, 4];

console.log(JSON.stringify(array));

array.sort(function (a, b) {

    console.log(a , b, JSON.stringify(array));

    return a - b;

});

console.log(JSON.stringify(array));

.as-console-wrapper { max-height: 100% !important; top: 0; }

what's the 'sort' method's difference between chrome environment and node environment

V8 developer here.

As some of the comments are getting at, this is not about Chrome vs. Node (which should behave the same way). It's due to a difference in V8 versions, where Chrome 74 already has the new behavior whereas Node 10 still has the old. Update to Node 11 and you'll see that same behavior there.

In the past, V8 used a combination of QuickSort (for larger arrays) and InsertionSort (for small arrays, up to 10 elements). InsertionSort just so happens to work correctly with the bad comparator function. Use a test array with 11 elements or more, and it will no longer sort correctly in Node 10.

(Versions of V8 since 7.4 now use TimSort for Array.prototype.sort.)

I know that that's not what this question is about, but for the record and/or anyone else reading this in the future: (pre, next) => pre <= next is not a good comparator function! In JavaScript, Array.prototype.sort expects a comparator that returns a number less than zero, equal to zero, or greater than zero, depending on whether the first argument is less than, equal to, or greater than the second. So the proper way to sort strings is something like:

my_string_array.sort((a, b) => {
  if (a < b) return -1;
  if (a > b) return 1;
  return 0;
});

When you use such a comparator, you will always get the right result, in all versions of Chrome and Node.

When you use a comparator that uses a single comparison and hence returns a boolean value, then true silently maps to 1 and false maps to 0, but that means it accidentally returns "equal" for a bunch of pairs that are not, in fact, equal, which can lead to quite surprising sorting results, especially when the engine uses an unstable sorting algorithm under the hood.

Sorting in JavaScript: Shouldn't Returning a Boolean Be Enough For a Comparison Function