Problem
Given a list of numbers, sort it using the Merge Sort algorithm.
Example
{
"arr": [5, 8, 3, 9, 4, 1, 7]
}
Output:
[1, 3, 4, 5, 7, 8, 9]
Solution
function merge(left, right) {
var mergedArr = [];
var leftIndex = 0;
var rightIndex = 0;
while(leftIndex < left.length && rightIndex < right.length) {
if(left[leftIndex] < right[rightIndex]) {
mergedArr.push[left[leftIndex]]
leftIndex++;
} else {
mergedArr.push[right[rightIndex]];
rightIndex++;
}
}
return mergedArr.concat(left.slice(leftIndex))
.concat(right.slice(rightIndex));
}
function merge_sort(arr) {
// Write your code here.
if (arr.length <= 1) {
return arr;
}
var middle = Math.floor(arr.length /2)
var left = arr.slice(0, middle);
var right = arr.slice(middle);
return merge(
merge_sort(left), merge_sort(right)
);
}