Merge Sort (Top-Down)

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

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this C++ DSA implementation can be compared directly with the other languages.

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;
}

Complexity

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

Implementation notes

Keep the explicit algorithmic steps instead of calling a standard-library sort. The replay is meant to expose comparisons, movement, and recursion.
The implementation is intentionally compact for learning and replay, not a production sorting utility.

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.