Skip to content

Instantly share code, notes, and snippets.

@sheniff
Created April 22, 2015 04:24
Show Gist options
  • Save sheniff/5074960c80782e084a11 to your computer and use it in GitHub Desktop.
Save sheniff/5074960c80782e084a11 to your computer and use it in GitHub Desktop.
MergeSort in JS
function mergeSort (arr, st, end) {
var res;
st = st || 0;
end = end || arr.length;
if(end - st > 1) {
var mid = st + Math.round((end - st)/2);
var a1 = mergeSort(arr, st, mid);
var a2 = mergeSort(arr, mid, end);
res = merge(a1, a2);
} else {
res = arr.slice(st, end);
}
return res;
}
function merge (arr1, arr2) {
var res = [];
var p1 = p2 = 0;
while(p1 < arr1.length && p2 < arr2.length) {
if(arr1[p1] < arr2[p2]) {
res.push(arr1[p1++]);
} else {
res.push(arr2[p2++]);
}
}
while(p1 < arr1.length) {
res.push(arr1[p1++]);
}
while(p2 < arr2.length) {
res.push(arr2[p2++]);
}
return res;
}
console.log(mergeSort([9,3,1,6,65,32,2,1,1,4,9]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment