DEV Community

Dumb Down Demistifying Dev
Dumb Down Demistifying Dev

Posted on • Edited on

3 3

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

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay