Merge Sort Algorithm in DSA C++

Mental Model

Split the list into halves until each part has one item, then merge parts back together in order.

Analogy: Imagine sorting a deck of cards by splitting it into small piles, sorting each pile, then carefully combining piles back into a sorted deck.

Unsorted array:
[38, 27, 43, 3, 9, 82, 10]
Split into halves:
[38, 27, 43]   [3, 9, 82, 10]
Each half split further until single elements:
[38] [27] [43]   [3] [9] [82] [10]

Dry Run Walkthrough

Input: array: [38, 27, 43, 3, 9, 82, 10]

Goal: Sort the array in ascending order using merge sort

Step 1: Split array into two halves

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

Why: We break the problem into smaller parts to sort easily

Step 2: Split left half into [38] and [27, 43]

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

Why: Keep splitting until each part has one element

Step 3: Split [27, 43] into [27] and [43]

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

Why: Single elements are considered sorted

Step 4: Merge [27] and [43] into sorted [27, 43]

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

Why: Combine sorted parts maintaining order

Step 5: Merge [38] and [27, 43] into sorted [27, 38, 43]

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

Why: Merge left half fully sorted

Step 6: Split right half [3, 9, 82, 10] into [3, 9] and [82, 10]

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

Why: Split right half to smaller parts

Step 7: Split [3, 9] into [3] and [9]

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

Why: Single elements are sorted

Step 8: Merge [3] and [9] into [3, 9]

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

Why: Merge sorted small parts

Step 9: Split [82, 10] into [82] and [10]

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

Why: Split until single elements

Step 10: Merge [82] and [10] into [10, 82]

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

Why: Merge sorted parts

Step 11: Merge [3, 9] and [10, 82] into [3, 9, 10, 82]

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

Why: Merge right half fully sorted

Step 12: Merge [27, 38, 43] and [3, 9, 10, 82] into fully sorted [3, 9, 10, 27, 38, 43, 82]

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

Why: Final merge produces fully sorted array

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    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];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

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

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

if (left < right) {

check if current segment has more than one element to split

int mid = left + (right - left) / 2;

find middle index to split array

mergeSort(arr, left, mid);

recursively sort left half

mergeSort(arr, mid + 1, right);

recursively sort right half

merge(arr, left, mid, right);

merge two sorted halves into one sorted segment

while (i < n1 && j < n2) {

compare elements from left and right subarrays to merge in order

arr[k] = L[i]; i++;

take element from left subarray if smaller or equal

arr[k] = R[j]; j++;

take element from right subarray if smaller

while (i < n1) { arr[k] = L[i]; i++; k++; }

copy remaining elements from left subarray if any

while (j < n2) { arr[k] = R[j]; j++; k++; }

copy remaining elements from right subarray if any

Output

3 9 10 27 38 43 82 

Complexity Analysis

Time: O(n log n) because the array is repeatedly split in half (log n splits) and merging takes linear time at each level

Space: O(n) because temporary arrays are used to merge sorted halves

vs Alternative: Compared to simple sorting like bubble sort O(n^2), merge sort is much faster for large data but uses extra space

Edge Cases

empty array

function returns immediately without changes

DSA C++

if (left < right) {

array with one element

function returns immediately as single element is already sorted

DSA C++

if (left < right) {

array with duplicate elements

duplicates are handled correctly and appear in sorted order

DSA C++

if (L[i] <= R[j]) {

When to Use This Pattern

When you need a reliable, fast sorting method that works well on large data and can be implemented recursively, reach for merge sort because it splits and merges efficiently.

Common Mistakes

Mistake: Not handling the base case properly causing infinite recursion
Fix: Add condition to stop recursion when segment size is 1 or 0: if (left < right)

Mistake: Incorrectly merging arrays causing out-of-bound errors
Fix: Use correct indices and copy remaining elements after main merge loop

Summary

It sorts an array by splitting it into halves, sorting each half, and merging them back in order.

Use it when you want a fast, stable sorting algorithm especially for large datasets.

The key insight is breaking the problem into smaller sorted parts and merging them carefully.