Sorting

Implement Merge Sort

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)
        );
}

Leave a comment