How To Do Merge Sort in JavaScript

Merge Sort is one of the most efficient sorting algorithms, especially for large datasets. It’s based on the divide and conquer approach, making it faster than simple algorithms like Bubble Sort or Selection Sort. This post will explore how to implement Merge Sort in JavaScript, walk through the algorithm step-by-step, and discuss its time and space complexities.

What is Merge Sort?

Merge Sort works by recursively dividing the array into two halves, sorting each half, and then merging the two sorted halves. This divide-and-conquer strategy ensures that each small problem (sorting two elements) is solved before merging them into a larger sorted array.

Pseudocode for Merge Sort

Here’s the pseudocode for Merge Sort:

procedure mergeSort(arr)
    if length(arr) <= 1 then
        return arr

    mid = length(arr) / 2
    left = mergeSort(arr[0..mid-1])
    right = mergeSort(arr[mid..end])

    return merge(left, right)

procedure merge(left, right)
    result = empty array
    while left is not empty and right is not empty do
        if left[0] <= right[0] then
            append left[0] to result
            remove left[0]
        else
            append right[0] to result
            remove right[0]
    append remaining elements of left and right to result
    return result

• Step-by-Step Explanation:
  • The array is divided into two halves until you have sub-arrays of size 1 or 0 (which are inherently sorted).
  • The merge step combines two sorted arrays into one sorted array by comparing elements from both halves.

Time Complexity of Merge Sort

• Best Case: O(n log n) – This occurs because the array is divided into halves (log n divisions), and each division requires a linear pass (n) to merge the two halves.
• Average Case: O(n log n) – Merge Sort always performs consistently, making it a reliable algorithm for sorting large datasets.
• Worst Case: O(n log n)—The worst-case performance is also O(n log n), which is one reason Merge Sort is preferred for large datasets.

Space Complexity of Merge Sort

• Space Complexity: O(n) – Merge Sort requires additional space equal to the size of the input array to hold the temporary merged arrays. This makes it less space-efficient than some in-place algorithms like Quick Sort.

JavaScript Implementation of Merge Sort

Here’s how you can implement Merge Sort in JavaScript:

// Function to merge two sorted arrays
function merge(left, right) {
    let result = [];
    let i = 0, j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }

    // Append the remaining elements of left and right (one of these will be empty)
    return result.concat(left.slice(i)).concat(right.slice(j));
}

// Recursive Merge Sort function
function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

// Example usage
const arr = [38, 27, 43, 3, 9, 82, 10];
console.log("Initial array:", arr);
console.log("Sorted array:", mergeSort(arr));

Explanation:

• mergeSort() recursively divides the array in half until individual elements are left.
• The merge() function takes two sorted arrays and merges them into one sorted array by comparing elements from both arrays.
• The sorted array is returned after all recursive calls are complete.

Output

Initial array: [
  38, 27, 43, 3,
   9, 82, 10
]
Sorted array: [
   3,  9, 10, 27,
  38, 43, 82
]

Step-by-Step Walkthrough of Merge Sort

Let’s walk through Merge Sort using the array [38, 27, 43, 3, 9, 82, 10].

Step 1: Divide the Array

The array is recursively divided into smaller sub-arrays:

1. [38, 27, 43, 3, 9, 82, 10]
   • Split into [38, 27, 43] and [3, 9, 82, 10]
   • Further split into [38] [27, 43] and [3, 9] [82, 10]
   • Continue splitting until you reach individual elements: [38] [27] [43] [3] [9] [82] [10]

---

Step 2: Merge Sub-arrays

Once the array is fully divided, we begin merging the sub-arrays:

1. Merge [27] and [43] to get [27, 43]
2. Merge [3] and [9] to get [3, 9]
3. Merge [82] and [10] to get [10, 82]

---

Step 3: Continue Merging

Now, the next round of merges combines the larger sub-arrays:

1. Merge [38] and [27, 43] to get [27, 38, 43]
2. Merge [3, 9] and [10, 82] to get [3, 9, 10, 82]

---

Step 4: Final Merge

Finally, we merge the two large sorted arrays:

1. Merge [27, 38, 43] and [3, 9, 10, 82] to get [3, 9, 10, 27, 38, 43, 82]

To see how Merge Sort works in practice, go to the Sorting Algorithm Visualizer!

Pros and Cons of Using Merge Sort

Pros:

1. Stable Sorting: Merge Sort maintains the relative order of equal elements, making it a stable sorting algorithm.
2. Efficient for Large Datasets: With O(n log n) time complexity, it’s one of the most efficient algorithms for sorting large datasets.
3. Consistent Performance: Unlike Quick Sort, Merge Sort consistently performs O(n log n) even in the worst case.

Cons:

1. Space Complexity: Merge Sort uses extra space proportional to the size of the array, making it less efficient in terms of space.
2. Overhead for Small Arrays: Due to the recursive overhead, Merge Sort may not be as fast as simpler algorithms like Insertion Sort for smaller arrays.

When to Use Merge Sort

Merge Sort is a great choice for:

1. Large Datasets: Merge Sort is a solid choice if you need consistent performance with large datasets due to its O(n log n) time complexity.
2. Linked Lists: Merge Sort performs well with linked lists since it does not require random access to elements.
3. Stable Sorting: Merge sort preserves the relative order of elements with equal values. Stability preserves data integrity, such as transactions with the same timestamp, and allows for data sorting by multiple attributes.

However, due to the overhead of recursion and extra space, algorithms like Quick Sort or Insertion Sort may be better suited for smaller arrays.

Conclusion

Merge Sort is a highly efficient sorting algorithm that performs consistently with O(n log n) time complexity. While it uses more space than in-place algorithms like Quick Sort, its predictable performance and stability make it a popular choice for sorting large datasets. By mastering Merge Sort, you can gain a strong understanding of the divide-and-conquer strategy and its applications in more advanced algorithms.

Congratulations on reading to the end of this tutorial!

Read the following articles to learn how to implement Merge Sort:

In Python – How to do Merge Sort in Python

In C++ – How to Do Merge Sort in C++

In Rust – How To Do Merge Sort in Rust

In Java – How to do Merge Sort in Java

Have fun and happy researching!