Merge Sort

What is Merge Sort?

Merge Sort is an efficient, stable, comparison-based sorting algorithm that follows the divide-and-conquer approach. It works by recursively dividing the unsorted list into sublists until each sublist contains a single element, then repeatedly merges these sublists to produce new sorted sublists until there is only one sorted list remaining.

How Does It Work?

Consider this unsorted array: [38, 27, 43, 3, 9, 82, 10]

Divide Phase:
  1. Split the array into two halves: [38, 27, 43] and [3, 9, 82, 10]
  2. Recursively split each half until single elements remain
Merge Phase:
  1. Merge single elements into sorted pairs: [27, 38], [3, 43], [9, 82], [10]
  2. Merge pairs: [3, 27, 38, 43] and [9, 10, 82]
  3. Final merge: [3, 9, 10, 27, 38, 43, 82]
Original: 
[38, 27, 43, 3, 9, 82, 10]
Divide:   
[38,27,43][3,9,82,10]
Divide:   
[38][27,43] | [3,9][82,10]
Divide:   
[38][27][43] | [3][9][82][10]
Merge:    
[27,38][43] | [3,9][10,82]
Merge:    
[27,38,43] | [3,9,10,82]
Final:    
[3,9,10,27,38,43,82]

Algorithm Steps

  1. Divide:
    • Find the middle point to divide the array into two halves
    • Recursively call merge sort on the first half
    • Recursively call merge sort on the second half
  2. Merge:
    • Create temporary arrays for both halves
    • Compare elements from each half and merge them in order
    • Copy any remaining elements from either half

Time Complexity

  • Best Case: O(n log n) (already sorted, but still needs all comparisons)
  • Average Case: O(n log n)
  • Worst Case: O(n log n) (consistent performance)

The log n factor comes from the division steps, while the n factor comes from the merge steps.

Space Complexity

Merge Sort requires O(n) additional space for the temporary arrays during merging. This makes it not an in-place sorting algorithm, unlike Insertion Sort or Bubble Sort.

Advantages

  • Stable sorting (maintains relative order of equal elements)
  • Excellent for large datasets (consistent O(n log n) performance)
  • Well-suited for external sorting (sorting data too large for RAM)
  • Easily parallelizable (divide steps can be done concurrently)

Disadvantages

  • Requires O(n) additional space (not in-place)
  • Slower than O(n²) algorithms for very small datasets due to recursion overhead
  • Not as cache-efficient as some other algorithms (e.g., QuickSort)

Merge Sort is particularly useful when sorting linked lists (where random access is expensive) and is the algorithm of choice for many standard library sorting implementations when stability is required. It's also commonly used in external sorting where data doesn't fit in memory.

Visualize the divide-and-conquer approach of Merge Sort with recursive splitting and merging.

Speed:1x
Comparisons:
0
Merges:
0

Main Array

Generate or enter an array to begin

Merge Sort Process

Steps:

  1. Divide array into halves recursively until single elements
  2. Merge adjacent subarrays in sorted order
  3. Continue merging until whole array is sorted

Test Your Knowledge before moving forward!

Merge Sort Quiz Challenge

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Merge Sort Implementation

// Merge Sort in JavaScript
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);
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex++]);
    } else {
      result.push(right[rightIndex++]);
    }
  }
  
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// Usage
const arr = [38, 27, 43, 3, 9, 82, 10];
console.log("Original:", arr);
console.log("Sorted:", mergeSort(arr));

Explore Sorting Algorithms

Selection Sort

Bubble Sort

Insertion Sort

Quick Sort

Heap Sort