DEV Community

Dumb Down Demistifying Dev
Dumb Down Demistifying Dev

Posted on • Updated on

Merge Sort

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);
    }
Enter fullscreen mode Exit fullscreen mode

Discussion (0)