Skip to content

Instantly share code, notes, and snippets.

@motiooon
Created January 14, 2014 16:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save motiooon/8421292 to your computer and use it in GitHub Desktop.
Save motiooon/8421292 to your computer and use it in GitHub Desktop.
MergeSort in Javascript
function merge(left, right){
var li = 0;
var ri = 0;
var result = [];
while(li < left.length && ri < right.length){
if(left[li] < right[ri]){
result.push(left[li++])
}else{
result.push(right[ri++])
}
}
return result.concat(left.slice(li)).concat(right.slice(ri));
}
function mergeSort(arr){
// Terminal case: 0 or 1 item arrays don't need sorting
if (arr.length < 2) {
return arr;
}
var middle = Math.floor(arr.length/2);
var left = arr.slice(0,middle);
var right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
var arr_to_sort = [2,5,9,3,1,76,34,23,4];
console.log("arr_to_sort", arr_to_sort);
console.log("arr sorted", mergeSort(arr_to_sort));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment