Skip to content

Instantly share code, notes, and snippets.

@dandresfg
Created December 5, 2020 05:55
Show Gist options
  • Save dandresfg/1c84206ebbb1e79338c79b7d77465150 to your computer and use it in GitHub Desktop.
Save dandresfg/1c84206ebbb1e79338c79b7d77465150 to your computer and use it in GitHub Desktop.
This is my implementation of mergesort.
function merge(left, right){
const list = [];
while(left.length && right.length){
if(left[0] < right[0]){
list.push(left[0])
left.shift();
} else {
list.push(right[0])
right.shift();
}
}
if(left.length){
return list.concat(left);
} else {
return list.concat(right);
}
}
function mergeSort(arr){
if(arr.length <= 1){
return arr;
} else {
const middle = Math.floor(arr.length / 2);
let left = arr.slice(0, middle);
let right = arr.slice(middle, arr.length)
left = mergeSort(left)
right = mergeSort(right)
if(left[left.length-1] <= right[0] ){
return left.concat(right);
}
return merge(left, right);
}
}
mergeSort([4,3,5,6,9,8,4,5,11,1,2])
// (11) [ 1, 2, 3, 4, 4, 5, 5, 6, 8, 9, 11 ]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment