How “Merge Sort” works in JavaScript?

Hello there! Today, we will delve into the world of sorting algorithms, specifically focusing on the Merge Sort algorithm. We’ll use JavaScript to illustrate how this algorithm works. If you’re a beginner, don’t worry! This guide is designed to be simple and easy to understand.

---

What is Merge Sort?

Merge Sort is a popular sorting algorithm that follows the divide-and-conquer programming paradigm.

It works by repeatedly dividing the unsorted list into two halves until we reach a stage where we can no longer divide (i.e., we have individual elements). We then merge these individual elements back together in a sorted manner.

---

The Merge Sort Process

To understand Merge Sort, let’s consider a simple array of numbers:

[38, 27, 43, 3, 9, 82, 10]

Here’s how Merge Sort would tackle this:

1. Divide: Break the array into halves until you have arrays with single elements:

[38, 27, 43, 3, 9, 82, 10]
[38, 27, 43] and [3, 9, 82, 10]
[38] [27, 43] and [3, 9] [82, 10]
[38] [27] [43] and [3] [9] [82] [10]

2. Conquer (Merge): Starting from the smallest arrays, merge them back together in a sorted manner:

[27, 38] [43] and [3, 9] [10, 82]
[27, 38, 43] and [3, 9, 10, 82]
[3, 9, 10, 27, 38, 43, 82]

Voila! The array is sorted.

Now, let’s see how we can implement this algorithm in JavaScript.

---

Implementing Merge Sort in JavaScript

First, we need to create a function that can merge two sorted arrays into one sorted array. Let’s call this function merge:

function merge(left, right) {
    let resultArray = [],
        leftIndex = 0,
        rightIndex = 0;

    // Loop through both arrays, comparing elements and adding the smaller one to the resultArray
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            resultArray.push(left[leftIndex]);
            leftIndex++; // Move to the next element in the `left` array
        } else {
            resultArray.push(right[rightIndex]);
            rightIndex++; // Move to the next element in the `right` array
        }
    }

    // Concatenate the remaining elements from either `left` or `right` (if any)
    return resultArray
        .concat(left.slice(leftIndex))
        .concat(right.slice(rightIndex));
}

Next, we will create our mergeSort function:

function mergeSort(array) {
    // Base case: If the array has only one element, return it (already sorted)
    if (array.length === 1) {
        return array;
    }

    // Divide the array into two halves
    const middle = Math.floor(array.length / 2); // Find the middle index
    const left = array.slice(0, middle); // Split the array into left half
    const right = array.slice(middle); // Split the array into right half

    // Recursively call mergeSort on the left and right halves
    return merge(
        mergeSort(left), // Recursively sort the left half
        mergeSort(right) // Recursively sort the right half
    );
}

You can now sort an array by calling mergeSort with the array as an argument:

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));

And there you have it! You’ve successfully implemented the Merge Sort algorithm in JavaScript.

---

Breakdown

let’s break down the execution of the Merge Sort algorithm step by step for the array [38, 27, 43, 3, 9, 82, 10].

Step 1: Initial Array

Input Array: [38, 27, 43, 3, 9, 82, 10]

Step 2: Initial Split

• Divide the array into two halves: [38, 27, 43] and [3, 9, 82, 10].

Step 3: Further Division

• Divide [38, 27, 43] into [38], [27], [43].

• Divide [3, 9, 82, 10] into [3, 9], [82, 10].

Step 4: Merging Single Elements

• The individual elements are already sorted as each sub-array has only one element.

Step 5: Merging Sub-Arrays

• Merge [38] and [27] to get [27, 38].

• Merge [43] with [27, 38] to get [27, 38, 43].

• Merge [3] and [9] to get [3, 9].

• Merge [82] and [10] to get [10, 82].

Step 6: Final Merge

• Merge [3, 9] and [10, 82] to get [3, 9, 10, 82].

Step 7: Final Merging of Halves

• Merge [27, 38, 43] and [3, 9, 10, 82] to get the final sorted array: [3, 9, 10, 27, 38, 43, 82].

This process involves recursively splitting the array until it contains only single elements, then merging them back together in sorted order at each step until the final sorted array is obtained.

---

Conclusion

Merge Sort is an efficient, stable sorting algorithm that performs well on large data sets.

While it may seem complex at first, breaking it down step-by-step makes it easier to understand.

I hope this guide has helped illuminate the inner workings of Merge Sort, and that you now feel more comfortable with this essential algorithm.

🔥 Wait! 🔥

Give that like button some love! And if you’re feeling extra cheeky, hit follow too!

Follow me on Instagram: Click Here

Comments

[Dusan Petkovic]

The animation is great, I can almost understand it lol.. jk

I understand from a general perspective, these kinds of things need to be practiced a few times, maybe even without the code editor.

[Dusan Petkovic]

The code doesn't make it much easier to understand, so its probably always better to write down on paper

[Jaimal Dullat]

I agreed. Recursion is a confusing concept even for experienced developers. I know animation doesn't show how the Recursion works, it's just a general working of Merge Sort which helps to understand it a bit easier.