Merge sort

• divide and conquer
• recursion

---

var arr = [3, 2, 4, 1, 6, 0, 9, -10];
mergeSortAlg(arr);

function mergeSortAlg(arr) {
    var n = arr.length;

    // base condition
    // check the input
    if (n <= 1) return arr;

    var mid = Math.floor((n - 1) / 2);

    // get left ref
    // keep the same ref
    var leftArr = [];
    for (var i = 0; i <= mid; i++) {
        leftArr[i] = arr[i];
    }

    // ger right ref
    var rightArr = [];
    for (var i = mid + 1, j = 0; i < n; i++ , j++) {
        rightArr[j] = arr[i];
    }

    // recursion, calling itself
    mergeSortAlg(leftArr); 
    mergeSortAlg(rightArr);
    return merge(leftArr, rightArr, arr);
}

// Merge to sorted array
// Q: could be improved by binary search ?
function merge(left, right, arr) {
    var k = 0;
    var i = 0;
    var j = 0;

    var na = left.length;
    var nb = right.length;

    while (i < na && j < nb) {
        if (left[i] < right[j]) {
            arr[k] = left[i];
            i++;
            k++;
        } else if (left[i] > right[j]) {
            arr[k] = right[j];
            j++;
            k++;
        } else {
            arr[k] = left[i];
            k++;
            i++;

            arr[k] = right[j];
            k++;
            j++;
        }
    }

    // a still have 
    while (i < na) {
        arr[k] = left[i];
        k++;
        i++;
    }

    // b still have
    while (j < nb) {
        arr[k] = right[j];
        k++;
        j++;
    }

    return arr;
}

---

• learning resource
  https://www.youtube.com/watch?v=TzeBrDU-JaY