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

  • A+
Category:Languages

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] 

 


This sort works on your input array due to its small size and the 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 only 0 or 1 (the numerical version of false and true, respectively). If n1 is 9 and n2 is 3, the sort will incorrectly report them as even (because 9 < 3 === false or 0 in numerical terms). In other words, your sort leaves 9 and 3 "unchanged with respect to each other".

Adding prints to the sort will show you some of these incorrect comparisons:

var a  = [1,2,3,4,5,6,7,8,9,10,11];  a.sort(function (n1, n2) {   console.log(n1 < n2 ? `I'm sorting ${n2} as smaller than ${n1}` :                          `I'm sorting ${n1} and ${n2} as even`);     return n1 < n2; });  console.log(a);

If your array is shorter than 11 elements, Chrome V8 will perform an insertion sort rather than a quicksort:

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

Insertion sort performs enough direct comparisons that you're guaranteed a correct ordering with a comparator such as yours, whereas quicksort relies on transitive relationships between multiple elements using all three comparisons. This explains why all counterexample arrays posted in this thread have length > 10, which use at least one step of quicksort before switching to insertion sort and producing a (mostly) sorted array.

Here's a black box test of this; it's not proof, but easy to cook up in lieu of a white box test which plugs prints into V8's quicksort routine to find the discrepancy step:

const test = (a, times=100000) => {   while (times--) {     shuffle(a);     const b = a.slice(0);     a.sort((x, y) => x > y);     b.sort((x, y) => x - y);      if (!eq(a, b)) {       return false;     }   }    return true; };  const eq = (a, b) => {   for (let i = 0; i < a.length; i++) {     if (a[i] !== b[i]) {       return false;     }   }      return true; };  const shuffle = a => {   var i = a.length;    while (i) {     const r = ~~(Math.random() * i--);     const t = a[i];     a[i] = a[r];     a[r] = t;   } }  // insertion sort, length <= 10 console.log("insertion sort passed?", test([1,2,3,4,5,6,7,8,9,10]));  // this will cause v8 to quicksort, length > 10 console.log("quicksort passed?", test([1,2,3,4,5,6,7,8,9,10,11])); 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: