Merge Sort — Divide & Conquer

What does it solve?

Sort an array of elements efficiently. Merge Sort recursively divides the array into halves until each piece has one element (inherently sorted), then merges them back in sorted order.

It is stable (equal elements keep their original order) and guaranteed O(n log n) — unlike Quick Sort which can degrade to O(n²).

The two phases

// ① Divide: split until size 1
mergeSort(arr, l, r):
  mid = (l + r) / 2
  mergeSort(arr, l, mid)
  mergeSort(arr, mid+1, r)
  // ② Merge sorted halves
  merge(arr, l, mid, r)

Complexity

Time complexity

O(n log n)

log n levels of recursion × O(n) merge work per level. Guaranteed for all inputs.

Space complexity

O(n)

A temporary array of size n is needed during each merge step.

Examples & edge cases

Live animation

Active subarray (dividing) Being merged / placed Comparing elements Fully sorted segment

⏸ Waiting to start

Step — of —

Phase

—

Subarray

—

Comparisons

so far

Merges done

completed

Select an example and press Play to begin.

✓ Sorted!

Speed Medium

Step-by-step table

Step	Phase	Subarray [l..r]	Action	Array state	Note

C++ implementation

merge_sort.cpp

#include <bits/stdc++.h>
using namespace std;

void merge(vector<int>& arr, int l, int mid, int r) {
    vector<int> tmp;
    int i = l, j = mid + 1;

    // Pick smaller element from left or right half
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) tmp.push_back(arr[i++]);
        else                   tmp.push_back(arr[j++]);
    }
    // Drain remaining elements
    while (i <= mid) tmp.push_back(arr[i++]);
    while (j <= r)   tmp.push_back(arr[j++]);

    // Copy merged result back
    for (int k = 0; k < (int)tmp.size(); k++)
        arr[l + k] = tmp[k];
}

void mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;          // base case: 1 element
    int mid = l + (r - l) / 2;
    mergeSort(arr, l, mid);       // sort left half
    mergeSort(arr, mid + 1, r);  // sort right half
    merge(arr, l, mid, r);        // merge sorted halves
}

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(arr, 0, arr.size() - 1);
    for (int x : arr) cout << x << " ";  // 3 9 10 27 38 43 82
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars