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.

Answer 2

No need to mark this as an answer, since it's not javascript, and doesn't have introsort's depth check to switch to heapsort.

Example C++ quicksort. It uses median of 3 to choose pivot value, Hoare partition scheme, then excludes middle values == pivot (which may or may not improve time, as values == pivot can end up anywhere during partition step), and only uses recursion on the smaller partition, looping back on the larger partition to limit stack complexity to O(log2(n)) worst case. The worst case time complexity is still O(n^2), but this would require median of 3 to repeatedly choose small or large values, an unusual pattern. Sorted, or reverse sorted arrays are not an issue. If all values are the same, then time complexity is O(n). Adding a depth check to switch to heapsort (making this an introsort) would limit time complexity to O(n log(n)), but with a higher constant factor depending on how much heapsort path is used.

void QuickSort(uint32_t a[], size_t lo, size_t hi) {
    while(lo < hi){
        size_t i = lo, j = (lo+hi)/2, k = hi;
        uint32_t p;
        if (a[k] < a[i])            // median of 3
            std::swap(a[k], a[i]);
        if (a[j] < a[i])
            std::swap(a[j], a[i]);
        if (a[k] < a[j])
            std::swap(a[k], a[j]);
        p = a[j];
        i--;                        // Hoare partition
        k++;
        while (1) {
            while (a[++i] < p);
            while (a[--k] > p);
            if (i >= k)
                break;
            std::swap(a[i], a[k]);
        }
        i = k++;
        while(i > lo && a[i] == p)  // exclude middle values == pivot
            i--;
        while(k < hi && a[k] == p)
            k++;
        // recurse on smaller part, loop on larger part
        if((i - lo) <= (hi - k)){
            QuickSort(a, lo, i);
            lo = k;
        } else {
            QuickSort(a, k, hi);
            hi = i;
        }
    }
}

If space isn't an issue, then the merge sorts here may be better:

Native JavaScript sort performing slower than implemented mergesort and quicksort

If just sorting numbers, and again assuming space isn't an issue, radix sort would be fastest.

Answer 3

The fastest way to sort an array of numbers is to convert it to a TypedArray then call its sort function. The sort functions on typed arrays are numeric by default and much faster than Array.sort() with a comparison function.

const a = Array.from({length: 1<<20}, Math.random)
const b = Array.from(a)

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

console.time("nativeSort")
a.sort(comparisonFunction)
console.timeEnd("nativeSort")

console.time("typedSort")
let typedArray = Float32Array.from(b)
typedArray.sort()
console.timeEnd("typedSort")