So while I was checking out different flavors of quicksort after taking the Coursera Algorithms class I found out about a new version of quicksort that was much faster then I had anticipated.  Java 7 had recently modified their sort function to use a new algorithm called Dual Pivot Quicksort, so I thought I’d check it out.  I found a java version and recoded it to be javascript.  It works well, but currently only sorts integers and in ascending order.  Ideally I should modify it to work the same way the normal array sort algorithm works, that way I’d be comparing apples to apples.  I believe under the hood that the V8 javascript engine has upgraded to the new dual pivot algorithm, but it does have some additional checks and improved functionality where you can pass in the sorting algorithm, which may be why it’s consistently slower then my javascript version of dual pivot quicksort that I coded up.  It’s consistently 10%-50% faster then the default array.sort() algorithm.  The default sort is going to work well enough for 90% of your sorting cases, but if you are following the 10/90 rule and have narrowed down the bottleneck in your code and want to optimize sort, then I would advise taking this code and modifying it for your needs since it will always be faster then the default array.sort().  Check it out on JSPerf http://jsperf.com/javascript-quicksort-comparisons

Technically JS Perf says it’s ±10.25% faster then the default sort the last time I ran it, but it does vary quite a bit. My guess is that it probably varies based on how random the shuffle is.  I suppose it could be because we are comparing a lion to a cheetah….the default sort sorts any object, and lets you pass in the sorting function, while the dual pivot quicksort I coded up only works on integers and in ascending order, but I’d still say it’s worth looking into, ESPECIALLY if whatever language you are coding in hasn’t rewritten their quicksort to use the new algorithm.  I made it a single variable module, and you call it with DualPivotQuicksort.sort(arr). Here’s the code.

/******** 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;
}());

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