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);
}
Top comments (0)