**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:

`[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]`

- Split into

**Step 2: Merge Sub-arrays**

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

- Merge
`[27]`

and`[43]`

to get`[27, 43]`

- Merge
`[3]`

and`[9]`

to get`[3, 9]`

- Merge
`[82]`

and`[10]`

to get`[10, 82]`

**Step 3: Continue Merging**

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

- Merge
`[38]`

and`[27, 43]`

to get`[27, 38, 43]`

- Merge
`[3, 9]`

and`[10, 82]`

to get`[3, 9, 10, 82]`

**Step 4: Final Merge**

Finally, we merge the two large sorted arrays:

- 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**:

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

**Cons**:

**Space Complexity**: Merge Sort uses extra space proportional to the size of the array, making it less efficient in terms of space.**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:

**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.**Linked Lists**: Merge Sort performs well with linked lists since it does not require random access to elements.**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!

Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.