Merge Sort

A stable divide-and-conquer algorithm that divides the array into halves, recursively sorts them, and then merges the sorted halves.

Algorithm Information

Time Complexity

Best: O(n log n)
Average: O(n log n)
Worst: O(n log n)

Space Complexity

O(n)

Properties

• Stable sorting algorithm
• Divide-and-conquer approach
• Consistent O(n log n) performance
• Recursive implementation
1/72
Speed: 1x

Algorithm Code

1function mergeSort(arr, left = 0, right = arr.length - 1) {
2  if (left < right) {
3    // Find the middle point
4    const mid = Math.floor((left + right) / 2);
5    
6    // Recursively sort first and second halves
7    mergeSort(arr, left, mid);
8    mergeSort(arr, mid + 1, right);
9    
10    // Merge the sorted halves
11    merge(arr, left, mid, right);
12  }
13  return arr;
14}
15 
16function merge(arr, left, mid, right) {
17  // Create temp arrays for left and right subarrays
18  const leftArr = arr.slice(left, mid + 1);
19  const rightArr = arr.slice(mid + 1, right + 1);
20  
21  let i = 0, j = 0, k = left;
22  
23  // Merge the temp arrays back into arr[left..right]
24  while (i < leftArr.length && j < rightArr.length) {
25    if (leftArr[i] <= rightArr[j]) {
26      arr[k] = leftArr[i];
27      i++;
28    } else {
29      arr[k] = rightArr[j];
30      j++;
31    }
32    k++;
33  }
34  
35  // Copy remaining elements of leftArr[], if any
36  while (i < leftArr.length) {
37    arr[k] = leftArr[i];
38    i++;
39    k++;
40  }
41  
42  // Copy remaining elements of rightArr[], if any
43  while (j < rightArr.length) {
44    arr[k] = rightArr[j];
45    j++;
46    k++;
47  }
48}

Variable State

left:0
right:6
mid:0
i:0
j:0
k:0

Call Stack

mergeSort(0, 6)

Array Visualization

Watch how Merge Sort divides the array into smaller parts and merges them back in sorted order

640
341
252
123
224
115
906

Statistics

Comparisons0
Swaps0
Step1 / 72

Legend

Comparing Elements
Current Merge Position
Sorted Section
Unsorted

Starting Merge Sort algorithm

How Merge Sort Works

Master the divide-and-conquer paradigm through merge sort's elegant recursive approach and guaranteed O(n log n) performance.

Algorithm Overview

Merge Sort is a divide-and-conquer algorithm that works by recursively dividing the array into smaller subarrays until each subarray contains only one element, then merging these subarrays back together in sorted order. This approach guarantees O(n log n) performance in all cases.

🌲 Divide-and-Conquer Strategy

The algorithm follows three key steps: Divide the array into two halves,Conquer by recursively sorting each half, and Combine by merging the sorted halves. This creates a binary tree structure where each level represents a division, and the merging happens as we return up the recursion tree.

Step-by-Step Process

1

Divide Phase

Recursively split the array into two halves until each subarray contains only one element. Single elements are considered inherently sorted.

if (left < right) {
  const mid = Math.floor((left + right) / 2);
  mergeSort(arr, left, mid);
  mergeSort(arr, mid + 1, right);
}
2

Conquer Phase

The base case is reached when subarrays have one element. At this point, we begin the merging process as the recursive calls return.

Base Case: Arrays with one element are already sorted!
3

Merge Phase

Combine two sorted subarrays into a single sorted array by comparing elements from each subarray and selecting the smaller one.

while (i <= mid && j <= right) {
  if (arr[i] <= arr[j]) {
    temp[k++] = arr[i++];
  } else {
    temp[k++] = arr[j++];
  }
}
4

Copy Remaining Elements

After one subarray is exhausted, copy any remaining elements from the other subarray, then copy the merged result back to the original array.

Key Insight: The merge operation maintains stability - equal elements keep their relative order!

Understanding the Recursion Tree

Merge sort creates a binary tree of recursive calls:

Level 0:         [8,3,5,4,7,6,1,2]
Level 1:     [8,3,5,4]         [7,6,1,2]
Level 2:   [8,3] [5,4]       [7,6] [1,2]
Level 3: [8][3][5][4]     [7][6][1][2]
↑ Divide Phase ↑
↓ Merge Phase ↓
Level 2:   [3,8] [4,5]       [6,7] [1,2]
Level 1:     [3,4,5,8]         [1,2,6,7]
Level 0:         [1,2,3,4,5,6,7,8]

🌳 Tree Analysis

The tree has log n levels (height), and each level processes n elementsduring merging. This gives us the O(n log n) time complexity: n elements × log n levels = O(n log n).

Complete Implementation

Here's the complete merge sort implementation with detailed comments:

function mergeSort(arr, left = 0, right = arr.length - 1) {
    // Base case: single element or empty array
    if (left >= right) return;
    
    // Divide: find the middle point
    const mid = Math.floor((left + right) / 2);
    
    // Conquer: recursively sort both halves
    mergeSort(arr, left, mid);        // Sort left half
    mergeSort(arr, mid + 1, right);   // Sort right half
    
    // Combine: merge the sorted halves
    merge(arr, left, mid, right);
}

function merge(arr, left, mid, right) {
    // Create temporary arrays for left and right subarrays
    const leftArr = arr.slice(left, mid + 1);
    const rightArr = arr.slice(mid + 1, right + 1);
    
    let i = 0, j = 0, k = left;
    
    // Merge the temporary arrays back into arr[left..right]
    while (i < leftArr.length && j < rightArr.length) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }
    
    // Copy remaining elements of leftArr[], if any
    while (i < leftArr.length) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }
    
    // Copy remaining elements of rightArr[], if any
    while (j < rightArr.length) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

// Example usage:
const numbers = [64, 34, 25, 12, 22, 11, 90];
console.log("Original:", numbers);
mergeSort(numbers);
console.log("Sorted:", numbers);

Key Concepts & Properties

✅ Advantages

  • •Guaranteed O(n log n): Consistent performance for all inputs
  • •Stable sorting: Equal elements maintain their relative order
  • •Predictable performance: No worst-case degradation
  • •Parallelizable: Recursive calls can run in parallel
  • •External sorting: Works well with large datasets on disk

❌ Disadvantages

  • •Extra memory: Requires O(n) additional space
  • •Not in-place: Cannot sort with constant extra space
  • •Recursive overhead: Function call stack can be deep
  • •Not adaptive: Doesn't benefit from partially sorted data
  • •Cache performance: Non-sequential memory access patterns

🎯 Stability Guarantee

Merge sort is stable because during the merge phase, when two elements are equal, we always take from the left subarray first (arr[i] ≤ arr[j]). This ensures that equal elements from the left subarray appear before equal elements from the right subarray, preserving their original relative order.

Complexity Analysis

Best Case

O(n log n)

Even with sorted input, the algorithm still divides and merges all subarrays.

Average Case

O(n log n)

Consistent performance regardless of input distribution or initial order.

Worst Case

O(n log n)

No input can cause merge sort to perform worse than O(n log n).

Mathematical Analysis

Recurrence Relation: T(n) = 2T(n/2) + O(n)
Tree Height: log₂(n) levels
Work per Level: O(n) for merging
Total Time: O(n) × log₂(n) = O(n log n)
Space Complexity: O(n) - Temporary arrays for merging

When to Use Merge Sort

✅ Perfect for:

  • • Stable sorting required: When relative order of equal elements matters
  • • Guaranteed performance: When O(n log n) worst-case is critical
  • • Large datasets: Consistent performance on big data
  • • External sorting: Sorting data that doesn't fit in memory
  • • Parallel processing: Recursive structure enables parallelization
  • • Linked lists: Natural fit for linked list sorting

❌ Consider alternatives for:

  • • Memory-constrained systems: O(n) extra space requirement
  • • Small datasets: Insertion sort may be faster
  • • Nearly sorted data: Adaptive algorithms perform better
  • • In-place requirement: Use heap sort or in-place quick sort
  • • Cache-sensitive applications: Quick sort has better locality

🌐 Real-World Applications

Merge sort is used in Java's Arrays.sort() for object arrays,Python's Timsort (hybrid with merge sort), and external sorting algorithmsfor databases. It's the go-to choice when stability and predictable performance are more important than memory usage.

Divide-and-Conquer Paradigm

Merge sort is a perfect example of the divide-and-conquer algorithmic paradigm:

1. Divide

Split the problem into smaller subproblems of the same type

2. Conquer

Solve subproblems recursively until reaching base cases

3. Combine

Merge solutions of subproblems to solve the original problem

🧠 Learning Value

Understanding merge sort teaches fundamental concepts like recursion, divide-and-conquer thinking, and the trade-offs between time and space complexity. It's an excellent introduction to more advanced algorithms and serves as a building block for understanding other divide-and-conquer algorithms.