Introduction

Merge sort is an efficient, comparison-based sorting algorithm that uses a divide-and-conquer approach. It splits an unsorted array into smaller halves until each piece has only zero or one element, and then merges those pieces back together in sorted order.

Why Merge Sort?

Elementary sorting algorithms (bubble sort, selection sort, and insertion sort) run in $O(n^2)$ quadratic time. While they perform well on tiny arrays, they struggle as data grows:

• Sorting an array of 100,000 random items with bubble sort can take 20 seconds or more.
• Sorting that same array with merge sort takes a fraction of a second.

Merge sort cuts the time complexity from $O(n^2)$ down to $O(n \log n)$, making it capable of handling very large datasets efficiently.

How Merge Sort Works

Merge sort combines three steps: split, sort, and merge.

1. Divide: Split the array in half repeatedly until every sub-array has only 1 element (or 0).
2. Conquer: Since a 1-element array is already sorted, begin merging adjacent pairs.
3. Combine: Merge smaller sorted arrays into larger sorted arrays until one complete array remains.

Part 1: Merging Two Sorted Arrays

Before writing the main recursive sort, we need a helper function that takes two already-sorted arrays and merges them into a single sorted array.

Merging logic

1. Create an empty results array.
2. Use two pointers (i and j), both starting at index 0.
3. While both arrays still have elements to look at:
   • Compare arr1[i] with arr2[j].
   • Push the smaller value into results and move that pointer forward by 1.
4. Once one array runs out of elements, push all remaining elements from the other array into results.
5. Return results.

Implementation

const merge = (arr1, arr2) => {
  const results = [];
  let i = 0;
  let j = 0;

  // Compare elements from both arrays and push the smaller one
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      results.push(arr1[i]);
      i++;
    } else {
      results.push(arr2[j]);
      j++;
    }
  }

  // Add remaining elements from arr1 (if any)
  while (i < arr1.length) {
    results.push(arr1[i]);
    i++;
  }

  // Add remaining elements from arr2 (if any)
  while (j < arr2.length) {
    results.push(arr2[j]);
    j++;
  }

  return results;
};

Part 2: The Full Merge Sort Algorithm

With our merge helper in place, the recursive sorting function is surprisingly short:

1. Base Case: If the array length is 0 or 1, it is already sorted. Return the array.
2. Find the Midpoint: Use Math.floor(array.length / 2).
3. Split and Recurse:
   • Call mergeSort on the left half (array.slice(0, mid)).
   • Call mergeSort on the right half (array.slice(mid)).
4. Merge: Return merge(left, right).

Implementation

const mergeSort = (array) => {
  // Base case: arrays with 0 or 1 element are already sorted
  if (array.length <= 1) return array;

  const mid = Math.floor(array.length / 2);

  // Recursively sort the left and right halves
  const left = mergeSort(array.slice(0, mid));
  const right = mergeSort(array.slice(mid));

  // Merge the sorted halves together
  return merge(left, right);
};

Examples

Basic usage

const numbers = [10, 24, 76, 73];
console.log(mergeSort(numbers)); // [10, 24, 73, 76]

const dataset = [8, 3, 5, 4, 7, 6, 1, 2];
console.log(mergeSort(dataset)); // [1, 2, 3, 4, 5, 6, 7, 8]

Evaluating Merge Sort

Complexity analysis

Where does $O(n \log n)$ come from?

The time complexity is the combination of two operations:

1. The splits ($\log n$ levels): Every time we split an array in half, we divide the size by 2.

   • For an 8-element array: $8 \to 4 \to 2 \to 1$ (3 splits, because $2^3 = 8$).
   • For a 32-element array: $32 \to 16 \to 8 \to 4 \to 2 \to 1$ (5 splits, because $2^5 = 32$).
   • The number of split levels grows logarithmically: $O(\log n)$.

2. The merge work ($n$ per level): At each level of the tree, merging all the sub-arrays back together requires comparing and placing every single element once: $O(n)$ work per level.

Multiplying the $\log n$ levels by the $O(n)$ work per level gives a total time complexity of $O(n \log n)$.

Key Takeaways

• Divide and Conquer: Merge sort recursively breaks an array into smaller sub-arrays until reaching 1-element arrays, then merges them back in order.
• Two Distinct Parts: The algorithm pairs a linear merging helper (merge, $O(n)$) with recursive splitting (mergeSort, $\log n$ levels).
• Consistent $O(n \log n)$ Performance: Merge sort guarantees $O(n \log n)$ time across best, average, and worst cases, regardless of how the input data is initially arranged.
• Space Trade-off: Its speed comes at the cost of $O(n)$ additional memory to hold sub-arrays during sorting.