When sorting an array of numbers in JavaScript, I accidentally used < instead of the usual - -- but it still works. I wonder why?

Example:

var a  = [1,3,2,4]
a.sort(function(n1, n2){
    return n1<n2
})
// result is correct: [4,3,2,1]

And an example array for which this does not work (thanks for Nicolas's example):

[1,2,1,2,1,2,1,2,1,2,1,2]

When sorting an array of numbers in JavaScript, I accidentally used < instead of the usual - -- but it still works. I wonder why?

Example:

var a  = [1,3,2,4]
a.sort(function(n1, n2){
    return n1<n2
})
// result is correct: [4,3,2,1]

And an example array for which this does not work (thanks for Nicolas's example):

[1,2,1,2,1,2,1,2,1,2,1,2]

• javascript

Share Improve this question Follow edited Oct 6, 2018 at 13:43 Boann 50.1k1616 gold badges124124 silver badges152152 bronze badges asked Oct 5, 2018 at 18:07 KuanKuan 11.4k2525 gold badges101101 silver badges212212 bronze badges 10

• You could check it out by seeing what the numeric value of the return is. Noting that returning 0 has cross-browser implications. – Dave Newton Commented Oct 5, 2018 at 18:12
• 2 @usr2564301 return n2 - n1 – Jeto Commented Oct 5, 2018 at 18:14
• Possible duplicate of How to sort an array of integers correctly – Dexygen Commented Oct 5, 2018 at 18:18
• 2 One example on which it doesn't work is [1,2,1,2,1,2,1,2,1,2,1,2]. I don't know if short examples can fail. – NicolasB Commented Oct 5, 2018 at 18:26
• 1 @NicolasB short examples can't fail on V8 (see my answer). – ggorlen Commented Oct 5, 2018 at 19:47

 |  Show 5 more ments

5 Answers 5

Sorted by: Reset to default 9

This sort works on your input array due to its small size and the current implementation of sort in Chrome V8 (and, likely, other browsers).

The return value of the parator function is defined in the documentation:

• If pareFunction(a, b) is less than 0, sort a to an index lower than b, i.e. a es first.
• If pareFunction(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements.
• If pareFunction(a, b) is greater than 0, sort b to an index lower than a, i.e. b es first.

However, your function returns binary true or false, which evaluate to 1 or 0 respectively when pared to a number. This effectively lumps parisons where n1 < n2 in with n1 === n2, claiming both to be even. If n1 is 9 and n2 is 3, 9 < 3 === false or 0. In other words, your sort leaves 9 and 3 "unchanged with respect to each other" rather than insisting "sort 9 to an index lower than 3".

If your array is shorter than 11 elements, Chrome V8's sort routine switches immediately to an insertion sort and performs no quicksort steps:

// Insertion sort is faster for short arrays.
if (to - from <= 10) {
  InsertionSort(a, from, to);
  return;
}

V8's insertion sort implementation only cares if the parator function reports b as greater than a, taking the same else branch for both 0 and < 0 parator returns:

var order = parefn(tmp, element);
if (order > 0) {
  a[j + 1] = tmp;
} else {
  break;
}

Quicksort's implementation, however, relies on all three parisons both in choosing a pivot and in partitioning:

var order = parefn(element, pivot);
if (order < 0) {
  // ...
} else if (order > 0) {
  // ...
}
// move on to the next iteration of the partition loop

This guarantees an accurate sort on arrays such as [1,3,2,4], and dooms arrays with more than 10 elements to at least one almost certainly inaccurate step of quicksort.

---

Update 7/19/19: Since the version of V8 (6) discussed in this answer, implementation of V8's array sort moved to Torque/Timsort in 7.0 as discussed in this blog post and insertion sort is called on arrays of length 22 or less.

The article linked above describes the historical situation of V8 sorting as it existed at the time of the question:

Array.prototype.sort and TypedArray.prototype.sort relied on the same Quicksort implementation written in JavaScript. The sorting algorithm itself is rather straightforward: The basis is a Quicksort with an Insertion Sort fall-back for shorter arrays (length < 10). The Insertion Sort fall-back was also used when Quicksort recursion reached a sub-array length of 10. Insertion Sort is more efficient for smaller arrays. This is because Quicksort gets called recursively twice after partitioning. Each such recursive call had the overhead of creating (and discarding) a stack frame.

Regardless of any changes in the implementation details, if the sort parator adheres to standard, the code will sort predictably, but if the parator doesn't fulfill the contract, all bets are off.

After my initial ment, I wondered a little bit about how easy it is to find arrays for which this sorting method fails.

I ran an exhaustive search on arrays of length up to 8 (on an alphabet of size the size of the array), and found nothing. Since my (admittedly shitty) algorithm started to be too slow, I changed it to an alphabet of size 2 and found that binary arrays of length up to 10 are all sorted properly. However, for binary arrays of length 11, many are improperly sorted, for instance [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0].

// Check if 'array' is properly sorted using the "<" parator function
function sortWorks(array) {
    let sorted_array = array.sort(function(n1, n2) {
        return n1 < n2;
    });
    for (let i=0; i<sorted_array.length-1; i++) {
        if (sorted_array[i] < sorted_array[i+1]) return false;
    }
    return true;
}

// Get a list of all arrays of length 'count' on an alphabet of size 'max_n'.
// I know it's awful, don't yell at me :'(
var arraysGenerator;
arraysGenerator = function (max_n, count) {
    if (count === 0) return [[]];
    let arrays = arraysGenerator(max_n, count-1);
    let result = [];
    for (let array of arrays) {
        for (let i = 0; i<max_n; i++) {
            result.push([i].concat(array));
        }
    }
    return result;
}

// Check if there are binary arrays of size k which are improperly sorted,
// and if so, log them
function testArraysOfSize(k) {
    let arrays = arraysGenerator(2, k);
    for (let array of arrays) {
        if (!sortWorks(array)) {
            console.log(array);
        }
    }
}

I'm getting some weird false-positives for some reason though, not sure where my mistake is.

---

EDIT:

After checking for a little while, here's a partial explanation on why OP's "wrong" sorting method works for lengths <=10 and for lengths >=11: it looks like (at least some) javascript implementations use InsertionSort if the array length is short (length <= 10) and QuickSort otherwise. It looks like QuickSort actively uses the "-1" outputs of the pare function while InsertionSort does not and relies only on the "1" outputs.

Source: here, all thanks to the original author.

If we analyze what's being done, it seems that this is mostly luck as in this case, 3 and 2 are considered to be "the same" and should be interchangeable. I suppose in such cases, the JS engines keep the original order for any values that have been deemed equal:

let a = [1, 3, 2, 4];
a.sort((n1, n2) => {
  const result = n1 < n2;
  if (result < 0) {
    console.log(`${n1} es before ${n2}`);
  } else if (result > 0) {
    console.log(`${n2} es before ${n1}`);
  } else {
    console.log(`${n1} es same position as ${n2}`);
  }
  return result;
})

console.log(a);

As pointed out in the ments, this isn't guaranteed to work ([1,2,1,2,1,2,1,2,1,2,1,2] being a counter-example).

Depending on exact sort() implementation, it is likely that it never checks for -1. It is easier and faster, and it makes no difference (as sorting is not guaranteed to be stable anyway, IIRC).

If the check sort() makes internally is pareFunction(a, b) > 0, then effectively true is interpreted as a > b, and false is interpreted as a <= b. And then your result is exactly what one would expect.

Of course the key point is that for > parison true gets covered to 1 and false to 0.

Note: this is all speculation and guesswork, I haven't confirmed it experimentally or in browser source code - but it's reasonably likely to be correct.

Sort function expects a parator which returns a number (negative, zero, or positive).

Assuming you're running on top of V8 engine (Node.js, Chrome etc.), you can find in array implementation that the returned value is pared to 0 (yourReturnValue > 0). In such case, the return value being casted to a number, so:

• Truthy values are converted to 1
• Falsy values are converted to 0

So based the documentation and the above, your function will return a sorted array in descending order in your specific case, but might brake in other cases since there's no regard to -1 value.