What is the fastest way to sort a large(ish) array of numbers in JavaScript

Question

In my application, I need to sort large arrays (between 100,000 and 1,000,000) of random numbers.

I've been using the built in array.sort(comparisonFunction) where comparisonFunction looks like this:

function comparisonFunction(a,b) {
    return a-b;
}

This works just fine, but I've read (e.g., Native JavaScript sort performing slower than implemented mergesort and quicksort) that there are faster options, especially if your requirements meet certain conditions:

1. I only need to sort numbers (e.g., not objects, or alphanumeric data)
2. The data is random (no chance that it's already ordered)
3. The sort doesn't need to be stable

So - what is the fastest (or close enough) sort algorithm available under those circumstances?

And, is there a canonical (or at least a relatively ideal) JavaScript implementation?

[UPDATE]

So, a quick clarification - in the linked question, the OP required a stable sort. Since I don't - I'm wondering if that would change the answer (i.e., perhaps there's a faster sort option available if you know in advance that your data will not be pre-sorted, and you don't need a stable sort).

Perhaps the answer is "no", but that's why I'm asking.

[UPDATE #2]

Here's an implementation of quicksort that, unless I've made a mistake - beats the native sort function handily:

function comparisonFunction(a, b) {
  return a - b;
}

function quickSort(arr, leftPos, rightPos, arrLength) {
  let initialLeftPos = leftPos;
  let initialRightPos = rightPos;
  let direction = true;
  let pivot = rightPos;
  while ((leftPos - rightPos) < 0) {
    if (direction) {
      if (arr[pivot] < arr[leftPos]) {
        quickSort.swap(arr, pivot, leftPos);
        pivot = leftPos;
        rightPos--;
        direction = !direction;
      } else
        leftPos++;
    } else {
      if (arr[pivot] <= arr[rightPos]) {
        rightPos--;
      } else {
        quickSort.swap(arr, pivot, rightPos);
        leftPos++;
        pivot = rightPos;
        direction = !direction;
      }
    }
  }
  if (pivot - 1 > initialLeftPos) {
    quickSort(arr, initialLeftPos, pivot - 1, arrLength);
  }
  if (pivot + 1 < initialRightPos) {
    quickSort(arr, pivot + 1, initialRightPos, arrLength);
  }
}
quickSort.swap = (arr, el1, el2) => {
  let swapedElem = arr[el1];
  arr[el1] = arr[el2];
  arr[el2] = swapedElem;
}

var
  i,
  arr1, arr2,
  length;

length = 1000000;


arr1 = [];
arr2 = [];
for (i = 0; i < length; i++) {
  arr1.push(Math.random());
  arr2.push(Math.random());
}

console.time("nativeSort");
arr1.sort(comparisonFunction);
console.timeEnd("nativeSort");


console.time("quickSort");
quickSort(arr2, 0, length - 1, length);
console.timeEnd("quickSort");

Answer 1

There are sort implementations that consistently beat the stock .sort (V8 at least), node-timsort being one of them. Example:

var SIZE = 1 << 20;

var a = [], b = [];

for(var i = 0; i < SIZE; i++) {
    var r = (Math.random() * 10000) >>> 0;
    a.push(r);
    b.push(r);
}

console.log(navigator.userAgent);

console.time("timsort");
timsort.sort(a, (x, y) => x - y);
console.timeEnd("timsort");

console.time("Array#sort");
b.sort((x, y) => x - y);
console.timeEnd("Array#sort");

<script src="https://rawgithub.com/mziccard/node-timsort/master/build/timsort.js"></script>

Here are some timings from different browsers I have around (Chakra anyone?):

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/53.0.2785.113 Safari/537.36
timsort: 256.120ms
Array#sort: 341.595ms

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/602.2.14 (KHTML, like Gecko) Version/10.0.1 Safari/602.2.14
timsort: 189.795ms
Array#sort: 245.725ms

Mozilla/5.0 (Macintosh; Intel Mac OS X 10.11; rv:51.0) Gecko/20100101 Firefox/51.0
timsort: 402.230ms
Array#sort: 187.900ms

So, the FF engine is very different from Chrome/Safari.