Merge Sort (Top-Down)

Split the array recursively, sort each half, then merge two sorted runs into one sorted result.

Algorithm

Basic Implementation

basic.cpp

#include <iostream>
#include <vector>

void merge(std::vector<int>& arr, int left, int mid, int right) {
    std::vector<int> tmp;
    int i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) tmp.push_back(arr[i++]);
        else tmp.push_back(arr[j++]);
    }
    while (i <= mid) tmp.push_back(arr[i++]);
    while (j <= right) tmp.push_back(arr[j++]);
    for (size_t k = 0; k < tmp.size(); ++k) arr[left + k] = tmp[k];
}

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

int main() {
    std::vector<int> arr{5, 1, 4, 2, 8};
    merge_sort(arr, 0, static_cast<int>(arr.size()) - 1);
    std::cout << "[";
    for (size_t i = 0; i < arr.size(); ++i) {
        if (i > 0) std::cout << ", ";
        std::cout << arr[i];
    }
    std::cout << "]" << std::endl;
    return 0;
}

The pinned input is [5, 1, 4, 2, 8]. The diagrams show the split into recursive halves, the sorted subarrays, and the final merge choices.

Step 1 - Split the input

The first midpoint splits [5, 1, 4, 2, 8] into left [5, 1] and right [4, 2, 8].

Step 2 - Sorted halves return

Recursive calls return [1, 5] and [2, 4, 8] before the final merge begins.

Step 3 - Merge by taking smaller fronts

Take 1 from left, then 2 and 4 from right, then the remaining 5 and 8.

Complexity

Time: O(n log n)
Space: O(n)
Stable: yes

Implementation notes

In C++, the input is a std::vector<int> initialized as {5, 1, 4, 2, 8} and passed by non-const reference to merge_sort(std::vector<int>& arr, int left, int right).
Recursive bounds are int indexes. mid is computed as left + (right - left) / 2, and the base case returns when left >= right.
merge(std::vector<int>& arr, int left, int mid, int right) allocates a temporary std::vector<int> tmp, pushes merged values into it, then copies them back with arr[left + k] = tmp[k].
Merge cursors i and j stay within left..mid and mid+1..right; ties use arr[i] <= arr[j], so the left run wins equal values.
The trace records the split [5, 1] and [4, 2, 8], sorted halves [1, 5] and [2, 4, 8], and the final merge to [1, 2, 4, 5, 8].
Output is streamed with std::cout, a size_t print loop, comma separators, and std::endl. Visible allocation is the input vector plus per-merge temporary buffers; mutation happens when merged values are copied back.

divide and conquer Each recursive call solves a smaller sorted subproblem.

merge step Two sorted halves are combined by repeatedly taking the smaller front item.