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

How “Merge Sort” works in JavaScript?