What is the fastest way to sort a large(ish) array of numbers in JavaScript
09:02 21 Nov 2016

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");

javascript arrays sorting