# Javascript Quicksort Comparisons

## JavaScript performance comparison

Revision 3 of this test case created by stacey reiman

## Preparation code

``````

<script>
Benchmark.prototype.setup = function() {
var arr = [];
var n = 200000; //array size we are sorting

for (var i = 0; i < n; i++) {
arr.push(parseInt(Math.random() * 10000));
}

/********************************************* SHUFFLE *****************************************************************/
//Fisher-Yates...aka..Knuth Shuffle
function shuffle(arr) {

var currentIndex = arr.length;
var temporaryValue;
var randomIndex;

// While there remain elements to shuffle...
while (0 !== currentIndex) {

// Pick a remaining element...
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;

// And swap it with the current element.
temporaryValue = arr[currentIndex];
arr[currentIndex] = arr[randomIndex];
arr[randomIndex] = temporaryValue;
}

return arr;
}
/*********************************** RECURSIVE QUICK SORT *************************************************************/
var StandardRecursiveQuicksort = (function() {

var standardRecursiveQS = {};

standardRecursiveQS.sort = function(arr) {
if (arr.length <= 1) {
return arr;
}
return recursiveQuickSort(arr, 0, arr.length - 1);
}

function recursiveQuickSort(arr, left, right) { //partition arrays so that everything to the left of pivot is less then pivot, and everything to the right is greater then pivot
var i = left;
var j = right;
var tmp;
var pivotidx = (left + right) / 2;
var pivot = parseInt(arr[pivotidx.toFixed()]);
/* partition */
while (i <= j) {
while (parseInt(arr[i]) < pivot)
i++;
while (parseInt(arr[j]) > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}

/* recursion */
if (left < j)
recursiveQuickSort(arr, left, j);
if (i < right)
recursiveQuickSort(arr, i, right);
return arr;
}
return standardRecursiveQS;
}());

/**********************************************************************************************************************/
/*************************************** Three Way Partition Quicksort ************************************************/
var ThreeWayPartitionQuicksort = (function() {

var ThreeWayPartionQuicksortModule = {};

//Private Variables
var CUTOFF = 8;  // cutoff to insertion sort, must be >= 1

ThreeWayPartionQuicksortModule.sort = function( a, lo, hi) { //Public function

if(typeof lo == "undefined" && typeof hi === "undefined"){
this.sort(a, 0, a.length - 1);
} else{
var N = hi - lo + 1;

// cutoff to insertion sort
if (N <= CUTOFF) {
insertionSort(a, lo, hi);
return;
}

// use median-of-3 as partitioning element
else if (N <= 40) {
var m = median3(a, lo, lo + N/2, hi);
exch(a, m, lo);
}

// use Tukey ninther as partitioning element
else  {
var eps = N/8; //TODO: verify these come out as integers
var mid = lo + N/2;
var m1 = median3(a, lo, lo + eps, lo + eps + eps);
var m2 = median3(a, mid - eps, mid, mid + eps);
var m3 = median3(a, hi - eps - eps, hi - eps, hi);
var ninther = median3(a, m1, m2, m3);
exch(a, ninther, lo);
}

// Bentley-McIlroy 3-way partitioning
var i = lo, j = hi+1;
var p = lo, q = hi+1;
var v = a[lo];
while (true) {
while (less(a[++i], v))
if (i == hi) break;
while (less(v, a[--j]))
if (j == lo) break;

// pointers cross
if (i == j && eq(a[i], v))
exch(a, ++p, i);
if (i >= j) break;

exch(a, i, j);
if (eq(a[i], v)) exch(a, ++p, i);
if (eq(a[j], v)) exch(a, --q, j);
}

i = j + 1;
for (var k = lo; k <= p; k++) exch(a, k, j--);
for (var k = hi; k >= q; k--) exch(a, k, i++);

this.sort(a, lo, j);
this.sort(a, i, hi);
}

}

// sort from a[lo] to a[hi] using insertion sort
function insertionSort( a, lo, hi) {
for (var i = lo; i <= hi; i++)
for (var j = i; j > lo && less(a[j], a[j-1]); j--)
exch(a, j, j-1);
}

// return the index of the median element among a[i], a[j], and a[k]
function median3( a, i, j, k) {
return (less(a[i], a[j]) ?
(less(a[j], a[k]) ? j : less(a[i], a[k]) ? k : i) :
(less(a[k], a[j]) ? j : less(a[k], a[i]) ? k : i));
}

/***********************************************************************
*  Helper sorting functions
***********************************************************************/

// is v < w ?
function less(v, w) {
return (v < w); //java version uses compareto
}

// does v == w ?
function eq(v, w) {
return (v == w); //java version uses compareto
}

// exchange a[i] and a[j]
function exch(a, i, j) {
var  swap = a[i];
a[i] = a[j];
a[j] = swap;
}

return ThreeWayPartionQuicksortModule;
}());

/**********************************************************************************************************************/
/*************************************** Dual Pivot QuickSort *********************************************************/

var DualPivotQuicksort = (function() {

var dualPivotQS = {};

dualPivotQS.sort = function(arr, fromIndex, toIndex) {
if(fromIndex === undefined && toIndex === undefined){
this.sort(arr, 0, arr.length);
} else{
rangeCheck(arr.length, fromIndex, toIndex);
dualPivotQuicksort(arr, fromIndex, toIndex - 1, 3);
}
return arr;
}

function rangeCheck(length, fromIndex, toIndex) {
if (fromIndex > toIndex) {
console.error("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
}
if (fromIndex < 0) {
console.error(fromIndex);
}
if (toIndex > length) {
console.error(toIndex);
}
}

function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

function dualPivotQuicksort( arr, left, right, div) {
var len = right - left;

if (len < 27) { // insertion sort for tiny array
for (var i = left + 1; i <= right; i++) {
for (var j = i; j > left && arr[j] < arr[j - 1]; j--) {
swap(arr, j, j - 1);
}
}
return;
}
var third = Math.floor(len / div); //TODO: check if we need to round up or down or just nearest

// "medians"
var m1 = left  + third;
var m2 = right - third;

if (m1 <= left) {
m1 = left + 1;
}
if (m2 >= right) {
m2 = right - 1;
}
if (arr[m1] < arr[m2]) {
swap(arr, m1, left);
swap(arr, m2, right);
}
else {
swap(arr, m1, right);
swap(arr, m2, left);
}
// pivots
var pivot1 = arr[left];
var pivot2 = arr[right];

// pointers
var less  = left  + 1;
var great = right - 1;

// sorting
for (var k = less; k <= great; k++) {
if (arr[k] < pivot1) {
swap(arr, k, less++);
}
else if (arr[k] > pivot2) {
while (k < great && arr[great] > pivot2) {
great--;
}
swap(arr, k, great--);

if (arr[k] < pivot1) {
swap(arr, k, less++);
}
}
}
// swaps
var dist = great - less;

if (dist < 13) {
div++;
}
swap(arr, less  - 1, left);
swap(arr, great + 1, right);

// subarrays
dualPivotQuicksort(arr, left,   less - 2, div);
dualPivotQuicksort(arr, great + 2, right, div);

// equal elements
if (dist > len - 13 && pivot1 != pivot2) {
for (var k = less; k <= great; k++) {
if (arr[k] == pivot1) {
swap(arr, k, less++);
}
else if (arr[k] == pivot2) {
swap(arr, k, great--);

if (arr[k] == pivot1) {
swap(arr, k, less++);
}
}
}
}
// subarray
if (pivot1 < pivot2) {
dualPivotQuicksort(arr, less, great, div);
}
}
return dualPivotQS;
}());

/**********************************************************************************************************************/

};

Benchmark.prototype.teardown = function() {
shuffle(arr);
};

</script>
``````

## Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
Quicksort 8 - assignment instead of push
``````function quickSort(arr) {

if (arr.length <= 1) {
return arr
}
var randomNumber = Math.floor(Math.random()* arr.length)
var medianArray = [
arr[0],
arr[Math.floor((arr.length)/2)],
arr[(arr.length)-1]
]

/* here we run a 2 pass bubble sort to find the median number...*/
var temp;
if (medianArray[0] > medianArray[1]) {
temp = medianArray[1]
medianArray[1] = medianArray[0]
medianArray[0] = temp
}
if (medianArray[1] > medianArray[2]) {
temp = medianArray[2]
medianArray[2] = medianArray[1]
medianArray[1] = temp
}

/* now we take the median number and grab the actual value of that
number in our current arr */

median = medianArray[1]
median = arr[median]
var pivotNumber =  arr.splice(median, 1)
var left = []
var right = []
var x = arr.length;

while (x--) {

if (arr[x] <= pivotNumber) {
left[left.length] = arr[x]
}
else {
right[right.length] = arr[x]
}
}
var leftSorted = quickSort(left)
var rightSorted = quickSort(right)
return leftSorted.concat(pivotNumber).concat(rightSorted)
}``````
pending…
Flash Sort 1
``````                 function flashSort(arr) {
var n = arr.length;
var i = 0, j = 0, k = 0, t;
var m = ~~( n * 0.125 );
var l = [];
var anmin = arr[ 0 ];
var nmax = 0;
var nmove = 0;

for ( i = 0; i < m; i++ ) {
l[ i ] = 0;
}

for ( i = 1; i < n; ++i ) {
if ( arr[ i ] < anmin ) anmin = arr[ i ];
if ( arr[ i ] > arr[ nmax ] ) nmax = i;
}

if ( anmin == arr[ nmax ]) return;

var c1 = ( m - 1 ) / ( arr[ nmax ] - anmin );

for ( i = 0; i < n; ++i ) {
k = ~~( c1 * ( arr[ i ] - anmin ) );
++l[ k ];
}

for ( k = 1; k < m; ++k ) {
l[ k ] += l[ k - 1 ];
}

var hold = arr[ nmax ];
arr[ nmax ] = arr[ 0 ];
arr[ 0 ] = hold;

var flash;
j = 0;
k = m - 1;
i = n - 1;

while ( nmove < i ) {
while ( j > ( l[ k ] - 1 ) ) {
k = ~~( c1 * ( arr[ ++j ] - anmin ) );
}
flash = arr[ j ];

while ( j != l[ k ] ) {
k = ~~( c1 * ( flash - anmin ) );
hold = arr[ ( t = l[ k ]-1) ];
arr[ t ] = flash;
flash = hold;
--l[ k ];
++nmove;
}
}

for( j = 1; j < n; ++j ) {
hold = arr[ j ];
i = j - 1;
while( i >= 0 && arr[i] > hold ) {
arr[ i + 1 ] = arr[ i-- ];
}
arr[ i + 1 ] = hold;
}
return arr
}
``````
pending…
Default Recursive Javascript Quicksort
``StandardRecursiveQuicksort.sort(arr);``
pending…
Three Way Partition Javascript Quicksort
``ThreeWayPartitionQuicksort.sort(arr);``
pending…
Dual Pivot Javascript Quicksort
``DualPivotQuicksort.sort(arr);``
pending…
Default Javascript Sort
``arr.sort(function(a, b){return a-b});``
pending…
Quicksort 5
``````function quickSort(arr) {
if (arr.length <= 1) {
return arr
}
var randomNumber = Math.floor(Math.random()* arr.length)
var pivotNumber = arr.splice(randomNumber, 1)
var left = []
var right = []

for (var x=0;x<arr.length;x++) {
if (arr[x] <= pivotNumber) {
left.push(arr[x])
}
else {
right.push(arr[x])
}
}
var leftSorted = quickSort(left)
var rightSorted = quickSort(right)
return leftSorted.concat(pivotNumber).concat(rightSorted)
}
``````
pending…
Quicksort 6 - reverse loop
``````function quickSort(arr) {
if (arr.length <= 1) {
return arr
}
var randomNumber = Math.floor(Math.random()* arr.length)
var pivotNumber = arr.splice(randomNumber, 1)
var left = []
var right = []
var x = arr.length;

while (x--) {

if (arr[x] <= pivotNumber) {
left.push(arr[x])
}
else {
right.push(arr[x])
}
}
var leftSorted = quickSort(left)
var rightSorted = quickSort(right)
return leftSorted.concat(pivotNumber).concat(rightSorted)
}
``````
pending…
Quicksort 7 - median pivot
``````function quickSort(arr) {

if (arr.length <= 1) {
return arr
}

var medianArray = [
arr[0],
arr[Math.floor((arr.length)/2)],
arr[(arr.length)-1]
]

/* here we run a 2 pass bubble sort to find the median number...*/
var temp;
if (medianArray[0] > medianArray[1]) {
temp = medianArray[1]
medianArray[1] = medianArray[0]
medianArray[0] = temp
}
if (medianArray[1] > medianArray[2]) {
temp = medianArray[2]
medianArray[2] = medianArray[1]
medianArray[1] = temp
}

/* now we take the median number and grab the actual value of that
number in our current arr */

median = medianArray[1]
median = arr[median]
var pivotNumber =  arr.splice(median, 1)
var left = []
var right = []
var x = arr.length;

while (x--) {

if (arr[x] <= pivotNumber) {
left.push(arr[x])
}
else {
right.push(arr[x])
}
}
var leftSorted = quickSort(left)
var rightSorted = quickSort(right)
return leftSorted.concat(pivotNumber).concat(rightSorted)
}``````
pending…

## Revisions

You can edit these tests or add even more tests to this page by appending `/edit` to the URL.