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:
- I only need to sort numbers (e.g., not objects, or alphanumeric data)
- The data is random (no chance that it's already ordered)
- 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);
