Merge Sort | Learn Data Structure with Shubham part 2

function mergeSort(array, left, right) {

if (array && (left < right)) {

const mid = Math.floor((left + right) / 2);

/* THIS CAN BE BY FLOOR ONLY, consider the case [0,1,2,3] mid = Math.ceil(0+3)/2 would be 2, will break the array [0,1,2] and [3] an un-even break */

if (left != mid) { /* optinal check, otherwise recustion with return this condition from the first if condition */

mergeSort(array, left, mid);

}

if (mid + 1 != right) { /* again optional condition */

mergeSort(array, mid + 1, right);

}

mergeSubArray(array, left, mid, mid + 1, right);

}

return array;

}

function mergeSubArray(array, left1, right1, left2, right2) {

let resultant = [], c1 = left1, c2 = left2;

while (c1 <= right1 && c2 <= right2) {

if (array[c1] < array[c2]) {

resultant.push(array[c1]);

c1++;

} else if (array[c2] < array[c1]) {

resultant.push(array[c2]);

c2++;

} else {

resultant.push(array[c1]);

c1++; c2++;/* both are same */

}

}

if (c1 > right1) {

while (c2 <= right2) {

resultant.push(array[c2]);

c2++;

}

}

if (c2 >= right2) {

while (c1 <= right1) {

resultant.push(array[c1]);

c1++;

}

}

for (let i = 0; i < resultant.length; i++) {

array[left1 + i] = resultant[i];

}

}

var arr = [100, 20, 9, 10, 15, 1, 2, 3];

mergeSort(arr, 0, arr.length - 1);

console.log(arr)

/*TODO: Does the merge subarray really require extra array? or can it be optimized */