Merge Sort: Algorithm, Pseudocode, Dry Run, Implementation, and Complexity

1. Why Do We Need Merge Sort? (The Problem with Naive Sorting)

Standard elementary sorting algorithms—such as Bubble Sort, Insertion Sort, and Selection Sort—operate with a worst-case and average-case time complexity of $\mathcal{O}(n^2)$. As dataset sizes scale up in modern applications, $\mathcal{O}(n^2)$ algorithms become computationally prohibitive.

Merge Sort is an advanced, highly optimized sorting algorithm that drastically improves time efficiency by leveraging a recursive strategy.

2. Core Mental Model: The "Divide and Merge" Principle

The fundamental premise of Merge Sort is captured in two core operations: Divide and Merge.

Real-Life Analogy: Imagine sorting a massive stack of 1,000 resumes. Instead of sorting the entire stack all at once (which is cumbersome and prone to error), you split the stack in half into two piles of 500. You keep splitting them down until every pile contains just a single resume. Because a single resume is inherently sorted, you then merge adjacent piles back together in sorted order, repeating the process until you have one fully sorted stack.

Merge Sort never explicitly carves out physical new arrays in memory during the split phase. Instead, it hypothetically divides the array by passing index boundaries (low and high) recursively.

3. High-Level Algorithm Workflow

To sort an array of size $n$, the algorithm follows a strict lifecycle:

4. Pseudocode Architecture

A. The Main Recursive Function (mergeSort)

The recursive function determines the midpoint of the current index range, recursively calls itself on both halves, and then invokes the merge utility.

function mergeSort(array, low, high):
    // Base Case: If the array has 1 or 0 elements, it is already sorted
    if low >= high:
        return
    
    // Find the middle index
    mid = low + (high - low) / 2
    
    // Recursively sort the left half
    mergeSort(array, low, mid)
    
    // Recursively sort the right half
    mergeSort(array, mid + 1, high)
    
    // Merge the two sorted halves
    merge(array, low, mid, high)

B. The Merge Function (merge)

The merge subroutine takes two sorted sub-arrays (low to mid and mid + 1 to high), compares their leading elements using two pointers, and places the smaller element into a temporary container.

function merge(array, low, mid, high):
    temporary_list = []
    left_pointer = low
    right_pointer = mid + 1
    
    // Compare elements from both halves and store the smallest in temporary storage
    while left_pointer <= mid and right_pointer <= high:
        if array[left_pointer] <= array[right_pointer]:
            temporary_list.append(array[left_pointer])
            left_pointer++
        else:
            temporary_list.append(array[right_pointer])
            right_pointer++
            
    // Copy remaining elements from the left half, if any
    while left_pointer <= mid:
        temporary_list.append(array[left_pointer])
        left_pointer++
        
    // Copy remaining elements from the right half, if any
    while right_pointer <= high:
        temporary_list.append(array[right_pointer])
        right_pointer++
        
    // Transfer sorted elements from temporary storage back to the original array
    for i from low to high:
        array[i] = temporary_list[i - low]

5. Step-by-Step Recursive Dry Run

Let us trace an array of size 5: [3, 1, 2, 4, 1] with indices low = 0 to high = 4.

1. Initial Call: mergeSort(arr, 0, 4)

   • mid = (0 + 4) / 2 = 2
   • Calls mergeSort(arr, 0, 2) (Left half: indices 0 to 2)
   • Calls mergeSort(arr, 3, 4) (Right half: indices 3 to 4)

2. Left Subtree Breakdown (0 to 2):

   • mergeSort(arr, 0, 2) -> mid = 1 -> Calls mergeSort(arr, 0, 1) and mergeSort(arr, 2, 2)
   • mergeSort(arr, 0, 1) -> mid = 0 -> Calls mergeSort(arr, 0, 0) and mergeSort(arr, 1, 1)
   • Base cases hit: Indices 0 and 1 return immediately (single elements [3] and [1]).
   • Merge 0 to 1: Compares 3 and 1. Result: [1, 3].
   • Merge 0 to 2: Merges [1, 3] with element at index 2 ([2]). Result: [1, 2, 3].

3. Right Subtree Breakdown (3 to 4):

   • mergeSort(arr, 3, 4) -> mid = 3 -> Calls mergeSort(arr, 3, 3) and mergeSort(arr, 4, 4)
   • Base cases hit: Single elements [4] and [1].
   • Merge 3 to 4: Compares 4 and 1. Result: [1, 4].

4. Final Grand Merge (0 to 4):

   • Left sorted half: [1, 2, 3]
   • Right sorted half: [1, 4]
   • Pointers compare elements sequentially until all elements are merged into the original array as [1, 1, 2, 3, 4].

6. Complete C++ Implementation

Here is the clean, production-grade C++ implementation demonstrating reference passing and vector-based temporary merging.

#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int>& arr, int low, int mid, int high) {
    vector<int> temp;
    int left = low;
    int right = mid + 1;

    // Merge elements in sorted order
    while (left <= mid && right <= high) {
        if (arr[left] <= arr[right]) {
            temp.push_back(arr[left]);
            left++;
        } else {
            temp.push_back(arr[right]);
            right++;
        }
    }

    // If elements remain on the left half
    while (left <= mid) {
        temp.push_back(arr[left]);
        left++;
    }

    // If elements remain on the right half
    while (right <= high) {
        temp.push_back(arr[right]);
        right++;
    }

    // Transfer back from temporary array to original array
    for (int i = low; i <= high; i++) {
        arr[i] = temp[i - low];
    }
}

void mergeSort(vector<int>& arr, int low, int high) {
    // Base case: 1 or 0 elements
    if (low >= high) {
        return;
    }

    int mid = low + (high - low) / 2;

    // Left recursion
    mergeSort(arr, low, mid);

    // Right recursion
    mergeSort(arr, mid + 1, high);

    // Merge sorted halves
    merge(arr, low, mid, high);
}

int main() {
    vector<int> arr = {3, 1, 2, 4, 1, 5, 2, 6, 4};
    int n = arr.size();

    mergeSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

7. Complexity Analysis

Time Complexity

• Division Steps ($\log_2 n$): At every recursive level, the array is split evenly in half. The number of times you can divide a dataset of size $n$ by 2 before reaching single elements is $\log_2 n$.
• Merging Work ($\mathcal{O}(n)$): At each level of recursion, the merge function traverses and compares elements across the sub-arrays. Across all sub-arrays at a given depth, the total work done during merging is linear ($\mathcal{O}(n)$).
• Total Time Complexity: $\mathcal{O}(n \log_2 n)$ across Best, Average, and Worst cases.

Space Complexity

• Temporary Storage: The algorithm utilizes a temporary vector during the merge process to hold elements in sorted order. In the worst-case scenario, this temporary storage requires $\mathcal{O}(n)$ auxiliary space.
• Call Stack Depth: The recursion stack goes as deep as $\log_2 n$, which requires $\mathcal{O}(\log n)$ stack memory.
• Total Space Complexity: $\mathcal{O}(n)$ due to the temporary array allocation.

8. Summary and Key Takeaways

• Paradigm Shift: Merge Sort replaces naive $\mathcal{O}(n^2)$ sorting with a divide-and-conquer recursive strategy yielding $\mathcal{O}(n \log n)$ performance.
• Virtual Partitioning: Instead of instantiating new physical sub-arrays in memory, the algorithm uses index boundaries (low, mid, high) to manage hypothetical sub-arrays.
• Base Case Safeguard: Recursion terminates immediately when low >= high, isolating single-element arrays that are inherently sorted.
• Two-Pointer Technique: The merge step uses dual pointers to compare leading elements of two sorted sub-arrays, picking the smallest iteratively.
• Leftover Copying: Once one sub-array's pointer is exhausted, remaining elements from the opposing sub-array are appended directly without further comparisons.
• In-Place Reference Transfer: Sorted elements residing in temporary storage are mapped back into the original array via index offset calculation (temp[i - low]).
• Logarithmic Depth: The division phase executes in $\log_2 n$ depth levels.
• Linear Merging: The combination phase requires linear time ($\mathcal{O}(n)$) per level, resulting in a final time complexity of $\mathcal{O}(n \log n)$.