What do we understand about Merge Sort?
 This is a Divide & Conquer algorithm
 It usually comprises of 2 functions
 main function recursively splits the Array into 2 halfs before merger
 2nd function is the actual merge function where it compares the left Array values with the right Array values
 there should be a counter that acts as the pointer for the 2 half Arrays
 returns a new Array instead of mutating the original Array

Good resource to continue reading up on:

Time Complexity:
 Height of the tree refers to the recursion part of the function  O(logn)
 Merge helper function  O(n)
 MergeSort worst  O(nlogn)

Space Complexity:
 O(n)
function merge (left, right) {
let x = 0;
let y = 0;
let output = [];
//! we check both the left and right pointers
//! if they have reached the end of their respective Arrays
while (x < left.length && y < right.length) {
//! COMPARE
if (left[x] < right[y]) {
output.push(left[x]);
x++; // next value to check if it is also smaller
} else {
output.push(right[y]);
y++; // bigger values comes in here
}
}
// left side leftovers from first loop
while (x < left.length) {
output.push(left[x]);
x++;
}
// right side leftovers from first loop
while (y < right.length) {
output.push(right[y]);
y++;
}
return output;
}
function MergeSort(arr, start = 0, end = arr.length) {
const arrayLength = arr.length;
if (arrayLength < 2) return arr;
const midindex = Math.floor(arrayLength / 2);
const left = MergeSort(arr.slice(start, mid));
const right = MergeSort(arr.slice(mid + 1, end));
return merge(left, right);
}
Discussion (0)