Skip to main content

​
Overview

Merge Sort is an efficient, stable, divide-and-conquer sorting algorithm. It divides the input array into two halves, recursively sorts them, and then merges the two sorted halves. Most implementations produce a stable sort, meaning that the order of equal elements is the same in the input and output.

​
Implementation

function merge(listA: number[], listB: number[]) {
  let temp: number[] = [];
  let i = 0;
  let j = 0;

  while (i < listA.length && j < listB.length) {
    temp.push(listA[i] < listB[j] ? listA[i++] : listB[j++]);
  }

  return [...temp, ...listA.slice(i), ...listB.slice(j)];
}

export function mergeSort(list: number[]): number[] {
  if (list.length < 2) {
    return list;
  }

  const splitAt = Math.floor(list.length / 2);

  return merge(
    mergeSort(list.slice(0, splitAt)),
    mergeSort(list.slice(splitAt))
  );
}

​
How It Works

  1. Divide: Split the array into two halves
  2. Conquer: Recursively sort each half
  3. Combine: Merge the two sorted halves into a single sorted array
  4. Base Case: Arrays with 0 or 1 elements are already sorted
Merge Sort’s divide-and-conquer approach guarantees O(n log n) performance in all cases, making it highly predictable.

​
Complexity Analysis

Time Complexity

  • Best Case: O(n log n)
  • Average Case: O(n log n)
  • Worst Case: O(n log n)
  • Guaranteed performance regardless of input

Space Complexity

  • Space: O(n) - requires additional arrays
  • Auxiliary: O(n) - for merging
  • Call Stack: O(log n) - for recursion

​
Usage Example

import { mergeSort } from './merge-sort';

// Example 1: Sort a simple array
const numbers = [38, 27, 43, 3, 9, 82, 10];
const sorted = mergeSort(numbers);
console.log(sorted); // [3, 9, 10, 27, 38, 43, 82]

// Example 2: Large array (where Merge Sort excels)
const large = Array.from({ length: 1000 }, () => Math.floor(Math.random() * 1000));
const sortedLarge = mergeSort(large);

// Example 3: Already sorted (still O(n log n))
const alreadySorted = [1, 2, 3, 4, 5];
mergeSort(alreadySorted); // [1, 2, 3, 4, 5]

// Example 4: Reverse sorted
const reverseSorted = [9, 7, 5, 3, 1];
mergeSort(reverseSorted); // [1, 3, 5, 7, 9]

​
Visual Example

Let’s trace through sorting [38, 27, 43, 3]: 
Divide Phase:
                [38, 27, 43, 3]
                /              \
          [38, 27]              [43, 3]
          /      \              /      \
        [38]    [27]          [43]    [3]

Conquer Phase (Merge):
        [38]    [27]          [43]    [3]
          \      /              \      /
          [27, 38]              [3, 43]
                \              /
                [3, 27, 38, 43]
Detailed merge steps: 
Merge [38] and [27]:
  Compare 38 and 27 → take 27
  Result: [27, 38]

Merge [43] and [3]:
  Compare 43 and 3 → take 3
  Result: [3, 43]

Merge [27, 38] and [3, 43]:
  Compare 27 and 3 → take 3
  Compare 27 and 43 → take 27
  Compare 38 and 43 → take 38
  Take remaining 43
  Result: [3, 27, 38, 43]

​
Characteristics

Merge Sort is stable - equal elements maintain their relative order in the output.
No, standard Merge Sort is not in-place. It requires O(n) additional space for merging. In-place variants exist but are more complex.
Standard Merge Sort is not adaptive - it performs the same number of operations regardless of input order. However, variants can be made adaptive.
No, Merge Sort is not online. It needs access to all elements before sorting.

​
When to Use

Merge Sort is excellent for large datasets, linked lists, and when stable sorting is required.
Good for:
  • Large datasets where O(n log n) performance is needed
  • When worst-case performance guarantees are important
  • Sorting linked lists (can be done in-place)
  • When stable sorting is required
  • External sorting (sorting data that doesn’t fit in memory)
  • Parallel processing (divide-and-conquer is easily parallelizable)
Avoid when:
  • Memory is extremely limited (requires O(n) extra space)
  • Sorting small arrays (overhead of recursion)
  • In-place sorting is strictly required

​
Performance Insights

Why Use Merge Sort?
  1. Predictable Performance: Always O(n log n), never degrades to O(n²)
  2. Stable: Maintains relative order of equal elements
  3. Parallelizable: Subproblems are independent
  4. Good for Linked Lists: Can be implemented without extra space for lists
  5. External Sorting: Excellent for sorting data on disk

​
Recursion Tree Analysis

For an array of size n:
  • Height of tree: log₂(n)
  • Work per level: O(n) - merging all elements
  • Total work: O(n) × O(log n) = O(n log n)

​
Code Walkthrough

​
Helper Function: merge()

function merge(listA: number[], listB: number[]) {
  let temp: number[] = [];
  let i = 0;  // Pointer for listA
  let j = 0;  // Pointer for listB

  // Merge by comparing elements
  while (i < listA.length && j < listB.length) {
    temp.push(listA[i] < listB[j] ? listA[i++] : listB[j++]);
  }

  // Append remaining elements
  return [...temp, ...listA.slice(i), ...listB.slice(j)];
}
The merge function combines two sorted arrays into one sorted array by comparing elements from both arrays.

​
Main Function: mergeSort()

export function mergeSort(list: number[]): number[] {
  // Base case: arrays with 0 or 1 element are already sorted
  if (list.length < 2) {
    return list;
  }

  // Divide: find middle point
  const splitAt = Math.floor(list.length / 2);

  // Conquer: recursively sort both halves and merge
  return merge(
    mergeSort(list.slice(0, splitAt)),    // Left half
    mergeSort(list.slice(splitAt))         // Right half
  );
}

​
Comparison with Other Sorts

AlgorithmBest CaseAverage CaseWorst CaseSpaceStablePredictable
Merge SortO(n log n)O(n log n)O(n log n)O(n)YesYes
Quick SortO(n log n)O(n log n)O(n²)O(log n)NoNo
Heap SortO(n log n)O(n log n)O(n log n)O(1)NoYes
Insertion SortO(n)O(n²)O(n²)O(1)YesNo

​
Variants

Bottom-Up Merge Sort: An iterative version that avoids recursion overhead by merging subarrays of size 1, then 2, then 4, etc.Natural Merge Sort: An adaptive variant that takes advantage of existing runs (sorted subsequences) in the input.Tim Sort: A hybrid algorithm (used by Python and Java) that combines Merge Sort with Insertion Sort for better real-world performance.

Build docs developers (and LLMs) love

Get started for freeTalk to us