A Voyage through Algorithms using Javascript

What is Merge Sort?

Merge Sort is a classic "divide and conquer" algorithm in computer science that breaks down a problem into smaller, more manageable parts. Unlike Bubble Sort and Insertion Sort, which slow down as the input size grows, Merge Sort maintains O(n log n) time complexity and handles larger datasets efficiently.

One of its key advantages is that it’s a stable sorting algorithm, meaning equal elements keep their original order. This can be useful in scenarios where stability matters, such as when sorting database records or ordered datasets.

The tone of this article is assumes you are already familiar with Recursion. If that’s not the case or you need a quick refreshment, I’d suggest you to start from the “A Voyage through Algorithms using Javascript - Recursion” article by following the link below, then come back and continue here later:

A Voyage through Algorithms using Javascript - Recursion

How Merge Sort Works

Merge Sort follows a clean, recursive approach:

Divide: Split the array into two halves, creating smaller and smaller subarrays.
Conquer: Recursively sort each subarray.
Combine: Merge the sorted subarrays back together to form a single sorted array.

Think of it this way: we shatter an array to pieces until each element becomes precisely a mini-array containing just that element, then with recursion we build it up again with a touch of comparison. The beauty of Merge Sort lies in its elegant process - first breaking down the problem completely, then building up the solution by merging sorted pieces back together.

Here's a visualization to make this clearer:

Modified (speed up) from Swfung8, licensed under CC BY-SA 3.0.

Implementing Merge Sort in JavaScript

Let's examine the implementation of Merge Sort in JavaScript, with detailed comments explaining each part:

const nums = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4];

function mergeSort(array) {
  /*
    Recursion exit condition: when there is only one item in the list, return the array.
    This is our base case - a single element array is already sorted.
    Each element in the array eventually ends up as a single element array: [99], [44], etc.
  */
  if (array.length === 1) {
    return array;
  }

  let left = [];
  let right = [];

  // Math.floor is used for a balanced split, making left <= right when odd-length.
  // This keeps recursion depth even, preventing unnecessary imbalance.
  let mid = Math.floor(array.length / 2);

  // Split array into left and right portions:
  for (let i = 0; i < mid; i++) {
    left.push(array[i]);
  }
  for (let i = mid; i < array.length; i++) {
    right.push(array[i]);
  }

  // Recursively sort both halves, then merge them
  // The || [] ensures we always pass an array even in edge cases
  // This prevents "Cannot read properties of undefined" errors
  return merge(mergeSort(left) || [], mergeSort(right) || []);
}

function merge(left, right) {
  // This function merges two arrays while keeping elements in order
  const mergedArr = [];

  // Use index pointers instead of shift() to maintain O(n) efficiency
  // shift() would cause O(n²) behavior due to array reindexing
  let i = 0; // index for left array
  let j = 0; // index for right array

  // Compare elements from both arrays and add the smaller one to result
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      mergedArr.push(left[i]);
      i++;
    } else {
      mergedArr.push(right[j]);
      j++;
    }
  }

  // Add any remaining elements from the left array
  // This triggers only when right array is exhausted but left still has elements
  while (i < left.length) {
    mergedArr.push(left[i]);
    i++;
  }

  // Add any remaining elements from the right array
  // This triggers only when left array is exhausted but right still has elements
  while (j < right.length) {
    mergedArr.push(right[j]);
    j++;
  }

  return mergedArr;
}

const answer = mergeSort(nums);
console.log("answer:", answer);
// Output: [1, 2, 4, 5, 6, 44, 63, 87, 99, 283]

As we can see from the implementation above, Merge Sort consists of two key functions:

The mergeSort function, which recursively splits the array into smaller parts until each subarray contains a single element.
The merge function, which compares elements from two sorted subarrays and merges them back into a single sorted array.

This separation of concerns makes the algorithm both elegant and powerful. At first, it can be overwhelming to follow what is happening and why it is happening. But there's more to Merge Sort than meets the eye. Let's look into some key implementation details that can help us to have a better mental model for understanding it's inner mechanics.

Key Implementation details for Merge Sort

Many explanations cover the basic mechanics of merge sort, but there are several technical aspects worth examining more closely for a complete understanding.

The Math.floor() Decision Point When Splitting Arrays

One detail that is often glossed over is the choice between Math.floor(), Math.ceil(), or regular integer division when splitting arrays. This decision significantly impacts algorithm behavior.

Using Math.floor() means that when the array length is odd, the left side gets one fewer element than the right. For example, with an array of length 5:

Math.floor(5/2) = 2, so left gets indices [0, 1] and right gets [2, 3, 4]

This creates a balanced recursion tree, which drives optimal performance. If we used Math.ceil(), we'd get an unbalanced split, potentially causing deeper recursion on one side and degrading performance.

Common Edge Cases

One error that can appear during studying Merge Sort might look like this:

TypeError: Cannot read properties of undefined (reading 'length')

This occurs because in certain edge cases, mergeSort(left) or mergeSort(right) might return undefined. A simple solution adds a failsafe:

return merge(mergeSort(left) || [], mergeSort(right) || []);

The || [] guarantees an array always reaches the merge function and eliminates the undefined length check errors.

Avoiding the O(n²) Performance Trap

When working with large amounts of data, certain built-in methods can introduce hidden performance costs. One common pitfall is using shift() to extract elements:

while (left.length && right.length) {
  mergedArr.push(left[0] < right[0] ? left.shift() : right.shift());
}

This approach has a serious flaw: shift() runs at O(n) complexity because it reindexes the entire array after each operation. When performed repeatedly throughout the sorting process, this creates O(n²) behavior, reducing Merge Sort's efficiency.

While using methods like slice() is convenient to simplify array splitting, they come with their own time and space complexity. Being mindful of how built-in functions operate can help avoid unnecessary overhead.

A more efficient approach for merging uses index pointers (i and j) to maintain O(n) complexity:

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

Time and Space Complexity Analysis

Merge Sort's performance characteristics are as follows:

Time Complexity:
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n log n)

This consistent performance across all scenarios makes Merge Sort highly reliable, unlike unstable sorting algorithms which can degrade in certain cases.

Space Complexity: O(n)

Merge Sort requires additional memory proportional to the input size. This is due to the creation of new arrays during the merge process.

Advantages and Disadvantages of Merge Sort

Advantages:

Predictable O(n log n) performance regardless of input data
Stable sorting (maintains relative order of equal elements)
Well-suited for linked lists and external sorting

Disadvantages:

O(n) extra space requirement
Slightly slower than Quicksort for in-memory sorting of arrays
Overkill for small arrays (where simpler algorithms might perform better)

When to Use Merge Sort

When you need stable sorting
When dealing with linked lists (Merge Sort is particularly efficient for linked lists)
When worst-case performance matters (unlike Quicksort, which can degrade to O(n²))
For external sorting, where data doesn't fit in memory

Practical Applications and Use Cases

Database systems: When sorting large datasets that don't fit in memory
External sorting: Used in systems that need to sort data stored on disk
Stable sorting requirements: When order of equal elements matters
Parallel computing: Merge Sort is easily parallelizable

Conclusion

Merge Sort is one of the most well-known examples of the "divide and conquer" approach, which powers many efficient algorithms. Even though it requires more memory than some sorting algorithms, its consistent performance and stability make it a solid choice for many applications.

Merge Sort might not be the go-to choice for every sorting need (especially with small arrays or when memory is constrained), understanding it deepens your algorithmic thinking and prepares you for dealing with more complex computational problems.

A Voyage through Algorithms using Javascript - Merge Sort