javascript - Why does sorting a JS array of numbers with < work?

Question

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]

Answer 1

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 comparator function is defined in the documentation:

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

However, your function returns binary true or false, which evaluate to 1 or 0 respectively when compared to a number. This effectively lumps comparisons 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 comparator function reports b as greater than a, taking the same else branch for both 0 and < 0 comparator returns:

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

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

var order = comparefn(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 comparator adheres to standard, the code will sort predictably, but if the comparator doesn't fulfill the contract, all bets are off.