Merge Sort

let array = [6, 5, 3, 1, 8, 7, 2, 4];
// let array = [99,44,6,2,1,5,63,87,283,4,0];
function mergeSort(arr) {
    // debugger;
    let len = arr.length;
    if (len <= 1) {
        return; //base case
    }
    
    let left = [];
    let right = [];
    let left_size = Math.floor(len / 2);
    let right_size = len - left_size;
    
    for (let i=0; i<left_size;i++) {
        left.push(arr[i]);
    }
    
    for (let i=left_size; i<len;i++) {
        right.push(arr[i]);
    }
    
    mergeSort(left);
    mergeSort(right);
    
    merge(arr, left, right);
}

function merge(arr, left, right) {
    let l = 0;
    let r = 0;
    let i = 0;
    while (l < left.length && r < right.length && i < arr.length) {
        if (left[l] < right[r]) {
            arr[i] = left[l];
            l++;
        } else {
            arr[i] = right[r];
            r++;
        }
        i++;
    }
    
    while (l < left.length) {
        arr[i] = left[l];
        l++;
        i++;
    }
    
    while (r < right.length) {
        arr[i] = right[r];
        r++;
        i++;
    }
}

mergeSort(array);
console.log(array);