Merge Sort in C++: Top-Down and Bottom-Up Approaches

Merge Sort is a classic divide-and-conquer algorithm that guarantees O(nlog⁡n)O(n \log n) performance in all cases. It works by recursively (or iteratively) splitting the array into smaller subarrays, sorting those subarrays, and then merging them to produce the final sorted array. Merge Sort is:

• Stable: preserves the relative order of equal elements
• Not in-place: requires O(n)O(n) extra space for merging

This post covers two variants:

1. Top-Down (Recursive) Merge Sort
2. Bottom-Up (Iterative) Merge Sort

---

1. Top-Down Merge Sort

Concept

1. If the array has one element, it is already sorted.
2. Otherwise:
   • Divide the array into two halves.
   • Recursively sort each half.
   • Merge the two sorted halves.

Step-by-Step Example

Original: [38, 27, 43, 3, 9, 82, 10]

Split into: [38, 27, 43, 3]  and  [9, 82, 10]

Recursively split [38,27,43,3] → [38,27] & [43,3]
[38,27] → [38] & [27] → merge → [27,38]
[43,3] → [43] & [3] → merge → [3,43]
Merge [27,38] & [3,43] → [3,27,38,43]

Similarly for [9,82,10] → [9,82] & [10]
[9,82] → merge → [9,82]
Merge [9,82] & [10] → [9,10,82]

Finally, merge [3,27,38,43] & [9,10,82]
→ [3,9,10,27,38,43,82]

Code Implementation

#include <vector>
#include <algorithm> // std::copy

void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    std::vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else              arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSortRecursive(std::vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSortRecursive(arr, left, mid);
    mergeSortRecursive(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

// Usage:
// std::vector<int> data = { ... };
// mergeSortRecursive(data, 0, data.size() - 1);

Analysis

• Time Complexity: O(nlog⁡n)O(n \log n) for all cases
• Space Complexity: O(n)O(n) extra space
• Stable: Yes
• Recursion depth: O(log⁡n)O(\log n)

---

2. Bottom-Up Merge Sort

Concept

Instead of recursion, this approach iteratively merges subarrays of size sz = 1, 2, 4, 8, ... until sz >= n:

1. For sz = 1; sz < n; sz *= 2:
2. For left = 0; left + sz < n; left += 2*sz:
   • mid = left + sz - 1
   • right = min(left + 2*sz - 1, n - 1)
   • Merge arr[left..mid] and arr[mid+1..right]

Code Implementation

#include <vector>
#include <algorithm>

void mergeSortBottomUp(std::vector<int>& arr) {
    int n = arr.size();
    std::vector<int> temp(n);
    
    for (int sz = 1; sz < n; sz *= 2) {
        for (int left = 0; left + sz < n; left += 2 * sz) {
            int mid = left + sz - 1;
            int right = std::min(left + 2*sz - 1, n - 1);
            
            // merge into temp
            int i = left, j = mid + 1, k = left;
            while (i <= mid && j <= right) {
                temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
            }
            while (i <= mid) temp[k++] = arr[i++];
            while (j <= right) temp[k++] = arr[j++];
            
            // copy back
            for (int p = left; p <= right; ++p)
                arr[p] = temp[p];
        }
    }
}

// Usage:
// std::vector<int> data = { ... };
// mergeSortBottomUp(data);

Analysis

• Time Complexity: O(nlog⁡n)O(n \log n)
• Space Complexity: O(n)O(n) extra space
• Stable: Yes
• No recursion: better control of stack usage

---

When to Use Which Variant?

Criterion	Top-Down	Bottom-Up
Simplicity	Easy to write	Slightly more code
Stack Depth	O(log⁡n)O(\log n) recursion	Constant (no recursion)
In-Place Preference	No	No
Adaptability	Easier to modify	Slightly more effort

---

Practice Exercises

1. Trace the top-down merge sort on the array [5, 1, 4, 2, 8] and list each merge step.
2. Implement merge sort for a linked list using bottom-up iteration.
3. Compare the performance (time and memory) of merge sort vs. quicksort on large random arrays.
4. Modify the recursive merge sort to switch to insertion sort when subarray size is below a threshold (e.g., 32).

---

Merge Sort is a powerful, reliable algorithm especially when stable sorting is required or when worst-case performance guarantees matter.