Skip to content

Instantly share code, notes, and snippets.

@0xKD
Created November 22, 2014 17:16
Show Gist options
  • Save 0xKD/d854dbf0837e5312faef to your computer and use it in GitHub Desktop.
Save 0xKD/d854dbf0837e5312faef to your computer and use it in GitHub Desktop.
Merge sort (variant) in JavaScript
(function(){
'use strict';
var randomArray = function(size) {
var arr = [];
for(var i=0;i<size;i++) {
arr.push(Math.round(Math.random() * size * 10));
}
return arr;
};
var merge = function(a, b) {
var c = [];
var l = a.length, m = b.length;
var i = 0, j = 0;
while(!(i == l && j == m)) {
if (i == l) {
c.push(b[j]);
j += 1;
} else if (j == m) {
c.push(a[i]);
i += 1;
} else {
if (a[i] < b[j]) {
c.push(a[i]);
i += 1;
} else {
c.push(b[j]);
j += 1;
}
}
}
return c;
};
var mergeSort = function(arr, p, r) {
// console.log('arr: ',arr,' | p: ',p,' | r: ',r);
if (p < r) {
var q = Math.floor((p + r) / 2);
// console.log('Mid:', q);
var ls = mergeSort(arr, p, q);
// console.log('ls:', ls);
var rs = mergeSort(arr, q+1, r);
// console.log('rs:', rs);
var merged = merge(ls, rs);
// console.log(ls,rs,'merged:', merged);
return merged;
} else {
return arr.slice(p, r+1);
}
};
var arr = randomArray(15);
var now = Date.now();
var r = mergeSort(arr, 0, arr.length);
console.log(r);
console.log(Date.now() - now);
}());
function n(n,o){for(c=[],l=n.length,m=o.length,z=x=0;z+x!=m+l;)c.push(z==l?o[x++]:x==m?n[z++]:n[z]<o[x]?n[z++]:o[x++]);return c}function s(l,o,c){var r=~~(o+c)/2;return c>o?n(s(l,o,r),s(l,r+1,c)):l.slice(o,c+1)}
// Usage: s([arr],0,<size>)
console.log(s([81,-7,3,-41,5],0,5))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment