Divide and Conquer: Merge Sort

Divide and conquer

• Divide – cut the vector in half.
• Conquer – sort each half with merge sort (recursion).
• Combine – merge the two sorted halves.

Think of it like this: Sorting a huge pile of exam papers with friends: each sorts a small pile, then you merge the sorted piles by always taking the smaller roll number from the tops.

#include <iostream>
#include <vector>
using namespace std;

void mergeSort(vector<int>& v, int lo, int hi) {      // sorts v[lo..hi)
    if (hi - lo <= 1) return;
    int mid = (lo + hi) / 2;
    mergeSort(v, lo, mid);
    mergeSort(v, mid, hi);
    vector<int> merged;
    int i = lo, j = mid;
    while (i < mid && j < hi) merged.push_back(v[i] <= v[j] ? v[i++] : v[j++]);
    while (i < mid) merged.push_back(v[i++]);
    while (j < hi) merged.push_back(v[j++]);
    for (int k = 0; k < (int)merged.size(); k++) v[lo + k] = merged[k];
}

int main() {
    vector<int> v = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(v, 0, v.size());
    for (int x : v) cout << x << ' ';
    cout << endl;
    return 0;
}

Output

3 9 10 27 38 43 82 

Why O(n log n)?

The vector can be halved about log₂ n times. At each level, merging touches all n items once. n × log n.

Merge sort is always O(n log n) and stable, but needs O(n) extra memory. std::stable_sort is a merge sort.