- A+

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])); `