# stable sort comparison (v5)

## 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

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