stable sort comparison

Benchmark created on


    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];
                        insert(array, begin_right, end, v, cmpFn);
    Array.prototype.swap=function(a, b)
        var tmp=this[a];
    function insert(array, begin, end, v, cmpFn)
        while(begin+1<end && cmpFn(array[begin+1], v) < 0) {
                array.swap(begin, begin+1);
    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 =, 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 wrapper.elem;
    var arr = randArr(400);

Test runner

Ready to run.

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


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