Divide and Conquer Sorting with Merge Sort in JavaScript

Elementary comparison sorts such as Bubble Sort, Selection Sort, and Insertion Sort are simple to write, but their quadratic O(n^2) time complexity makes them impractical once an array grows beyond a few thousand items.

Merge Sort solves this by applying a recursive divide-and-conquer strategy. It repeatedly splits an unsorted array in half until every subarray contains at most one element (which is inherently sorted), and then merges those smaller sorted arrays back together two at a time in O(n log n) time complexity.

Example #

Input : Unsorted array of numbers [38, 27, 43, 3, 9, 82, 10]
Output : New sorted array [3, 9, 10, 27, 38, 43, 82] in guaranteed O(n log n) time.

Test Cases:

mergeSort([38, 27, 43, 3, 9, 82, 10]);
// output: [3, 9, 10, 27, 38, 43, 82]

mergeSort([100, -20, 40, -30, 16, -100, -101]);
// output: [-101, -100, -30, -20, 16, 40, 100]

Implementation #

We break the algorithm into two focused functions:

1. mergeSort(array) recursively divides the input array at its midpoint until the base case (array.length <= 1) is reached.
2. merge(left, right) compares the front elements of two already-sorted arrays and combines them into a single sorted array in O(n) linear time.

function mergeSort(array) {
  // Base case: an array of 0 or 1 item is already sorted
  if (array.length <= 1) {
    return array;
  }

  const middleIndex = Math.floor(array.length / 2);
  const leftHalf = array.slice(0, middleIndex);
  const rightHalf = array.slice(middleIndex);

  return merge(mergeSort(leftHalf), mergeSort(rightHalf));
}

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  // Compare the smallest remaining elements of both halves
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // Append any remaining elements from either half
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }

  return result;
}

Main Point: Because splitting an array of length n in half takes log2(n) levels of recursion and merging all subarrays at each level visits n elements, Merge Sort always runs in O(n log n) time at the cost of O(n) auxiliary memory.

Credits #

Photo by Antoine Dautry

← Home