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)