stable sort comparison

JavaScript performance comparison

Test case created by

Preparation code


      
      <script>
Benchmark.prototype.setup = function() {
  // 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);

};
</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
augment native sort
stableSort(arr, function(a, b){
    return a - b;
});
pending…
full merge sort impl
merge_sort(arr, function(a, b){
    return a - b;
});
pending…

Compare results of other browsers

Revisions

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

0 Comments