stable sort comparison (v5)

Revision 5 of this benchmark created by pazams on October 28, 2015

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;
      });
  }
  
      function merge_sort2(array, cmpFn) {
  
        msort(array, 0, array.length);
  
        function msort(array, begin, end) {
          var size = end - begin;
          if (size < 2) return;
  
          var begin_right = begin + Math.floor(size / 2);
  
          msort(array, begin, begin_right);
          msort(array, begin_right, end);
          merge(array, begin, begin_right, end);
        }
  
        function merge(array, begin, begin_right, end) {
          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);
            }
          }
        }
  
        function insert(array, begin, end, v) {
          while (begin + 1 < end && cmpFn(array[begin + 1], v) < 0) {
            swap(array, begin, begin + 1);
            ++begin;
          }
          array[begin] = v;
        }
  
        function swap(array, a, b) {
          var tmp = array[a];
          array[a] = array[b];
          array[b] = tmp;
        }
  
      }
  
  
      function merge_sort3(array, cmpFn) {
        
        msort(array, 0, array.length, cmpFn);
  
  
        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);
            }
          }
        }
  
  
        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;
        }
  
  
      }
  
  
  var arr = randArr(5);

Test runner

stableSort(arr, function(a, b){
    return a - b;
});

merge_sort(arr, function(a, b){
    return a - b;
});

arr.sort(function(a, b){
    return a - b;
});

merge_sort2(arr, function(a, b){
    return a - b;
});

merge_sort3(arr, function(a, b){
    return a - b;
});

Revisions

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

• Revision 1: published on December 25, 2013
• Revision 5: published by pazams on October 28, 2015