CODEWITHSUNDEEP
javascriptarrayssorting
mattstuehler
mattstuehler

Reputation: 9282

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

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

Upvotes: 22

Views: 42080

Answers (4)

Alexander Nenashev
Alexander Nenashev

Reputation: 22802

2024 benchmark update:

` Chrome/130
---------------------------------------------------------------------------------------------
>                         n=100       |      n=1000      |     n=10000      |    n=100000    
OP's quicksort      ■ 1.00x x100k 160 | ■ 1.00x x10k 402 | ■ 1.00x  x1k 729 | ■ 1.00x x10  98
Float32Array#sort     3.08x x100k 492 |   1.66x x10k 667 |   1.27x  x1k 923 |   1.27x x10 124
timsort               4.56x x100k 730 |   3.48x  x1k 140 |   2.94x x100 214 |   2.83x x10 277
Array#sort            5.03x x100k 805 |   3.78x  x1k 152 |   2.77x x100 202 |   3.34x x10 327
--------------------------------------------------------------------------------------------- `

Open in the playground

const $chunk = () => Array.from({ length: 100 }, () => Math.random());
const $input =[];

// @benchmark timsort
let r;
timsort.sort(r = $input.slice(), (x, y) => x - y);
r;

// @benchmark Array#sort
$input.slice().sort((x, y) => x - y);

// @benchmark OP's quicksort
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;
}
// @run
let arr;
quickSort(arr = $input.slice(), 0, $input.length - 1, $input.length);
arr;

// @benchmark Float32Array#sort
[...new Float32Array($input).sort()]

/*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));
<script src="https://rawgithub.com/mziccard/node-timsort/master/build/timsort.js"></script>

Upvotes: 2

rotu
rotu

Reputation: 133

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

Upvotes: 10

rcgldr
rcgldr

Reputation: 28828

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.

Upvotes: 6

georg
georg

Reputation: 214959

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.

Upvotes: 15

Related Questions