stable sort comparison

Benchmark created on

Setup

// http://stackoverflow.com/questions/962802#962890
    function shuffle(array) {
      var tmp, current, top = array.length;
      if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
      }
      return array;
    }
    
    function randArr(num) {
        for (var a=[], i=0; i<num; ++i) a[i]=i;
        return shuffle(a);
    }
    
    function msort(array, begin, end, cmpFn)
    {
        var size=end-begin;
        if(size<2) return;
    
        var begin_right=begin+Math.floor(size/2);
    
        msort(array, begin, begin_right, cmpFn);
        msort(array, begin_right, end, cmpFn);
        merge(array, begin, begin_right, end, cmpFn);
    }
    
    function merge(array, begin, begin_right, end, cmpFn)
    {
        for(;begin<begin_right; ++begin) {
            if(cmpFn(array[begin], array[begin_right]) > 0) {
                        var v=array[begin];
                        array[begin]=array[begin_right];
                        insert(array, begin_right, end, v, cmpFn);
                }
        }
    }
    
    Array.prototype.swap=function(a, b)
    {
        var tmp=this[a];
        this[a]=this[b];
        this[b]=tmp;
    }
    
    function insert(array, begin, end, v, cmpFn)
    {
        while(begin+1<end && cmpFn(array[begin+1], v) < 0) {
                array.swap(begin, begin+1);
                ++begin;
        }
        array[begin]=v;
    }
    
    function merge_sort(array, cmpFn)
    {
        msort(array, 0, array.length, cmpFn);
    }
    
    function stableSort(arr, cmpFunc) {
        //wrap the arr elements in wrapper objects, so we can associate them with their origional starting index position
        var arrOfWrapper = arr.map(function(elem, idx){
            return {elem: elem, idx: idx};
        });
    
        //sort the wrappers, breaking sorting ties by using their elements orig index position
        arrOfWrapper.sort(function(wrapperA, wrapperB){
            var cmpDiff = cmpFunc(wrapperA.elem, wrapperB.elem);
            return cmpDiff === 0 
                 ? wrapperA.idx - wrapperB.idx
                 : cmpDiff;
        });
    
        //unwrap and return the elements
        return arrOfWrapper.map(function(wrapper){
            return wrapper.elem;
        });
    }
    
    
    var arr = randArr(400);

Test runner

Ready to run.

Testing in
TestOps/sec
augment native sort
stableSort(arr, function(a, b){
    return a - b;
});
ready
full merge sort impl
merge_sort(arr, function(a, b){
    return a - b;
});
ready

Revisions

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