C++ Program for Merge Sort with Example and Explanation

A C++ program for merge sort uses a mergeSort function to recursively split the array and a merge function to combine sorted parts; for example, void mergeSort(int arr[], int left, int right) splits and sorts the array.

Examples

Inputarr = {5, 2, 9, 1, 5, 6}

OutputSorted array: 1 2 5 5 6 9

Inputarr = {3, 1}

OutputSorted array: 1 3

Inputarr = {10}

OutputSorted array: 10

How to Think About It

To sort an array using merge sort, first think of dividing the array into two halves until each part has one element. Then, merge these small parts back together in sorted order by comparing elements from each half. This divide and conquer approach helps sort the entire array efficiently.

Algorithm

1

Check if the array has more than one element; if not, return.

2

Find the middle point to divide the array into two halves.

3

Recursively apply merge sort on the left half.

4

Recursively apply merge sort on the right half.

5

Merge the two sorted halves into a single sorted array.

Code

cpp

#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    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(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() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int size = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, size - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

Output

Sorted array: 1 2 5 5 6 9 

Dry Run

Let's trace the array {5, 2, 9, 1, 5, 6} through the merge sort code.

1

Initial split

Array is split into {5, 2, 9} and {1, 5, 6}

2

Split left half

Left half {5, 2, 9} splits into {5, 2} and {9}

3

Split left-left half

{5, 2} splits into {5} and {2}

4

Merge {5} and {2}

Merge to get sorted {2, 5}

5

Merge {2, 5} and {9}

Merge to get sorted {2, 5, 9}

6

Split right half

{1, 5, 6} splits into {1, 5} and {6}

7

Split right-left half

{1, 5} splits into {1} and {5}

8

Merge {1} and {5}

Merge to get sorted {1, 5}

9

Merge {1, 5} and {6}

Merge to get sorted {1, 5, 6}

10

Final merge

Merge {2, 5, 9} and {1, 5, 6} to get {1, 2, 5, 5, 6, 9}

Step	Array State
Initial	5 2 9 1 5 6
Split	5 2 9 | 1 5 6
Split	5 2 | 9 | 1 5 | 6
Merge	2 5 | 9 | 1 5 | 6
Merge	2 5 9 | 1 5 6
Final Merge	1 2 5 5 6 9

Why This Works

Step 1: Divide the array

The code uses mergeSort to split the array into halves recursively until each part has one element.

Step 2: Merge sorted halves

The merge function combines two sorted halves by comparing elements and placing them in order.

Step 3: Complete sorting

By merging all parts back, the entire array becomes sorted efficiently using the divide and conquer method.

Alternative Approaches

Iterative Merge Sort

cpp

#include <iostream>
using namespace std;

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int n) {
    for (int curr_size = 1; curr_size <= n-1; curr_size *= 2) {
        for (int left_start = 0; left_start < n-1; left_start += 2*curr_size) {
            int mid = min(left_start + curr_size - 1, n-1);
            int right_end = min(left_start + 2*curr_size - 1, n-1);
            merge(arr, left_start, mid, right_end);
        }
    }
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    mergeSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}

This uses loops instead of recursion, which can be easier to understand for some and avoids stack overhead.

Using std::vector and std::copy

cpp

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

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

int main() {
    vector<int> arr = {5, 2, 9, 1, 5, 6};
    mergeSort(arr);
    cout << "Sorted array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    return 0;
}

This approach uses C++ STL vectors and the <code>std::merge</code> function for cleaner code but may use more memory.

Complexity: O(n log n) time, O(n) space

Time Complexity

Merge sort divides the array into halves recursively (log n splits) and merges all elements (n per merge), resulting in O(n log n) time.

Space Complexity

It requires extra space to hold temporary arrays during merging, so space complexity is O(n).

Which Approach is Fastest?

Recursive and iterative merge sorts have similar time complexity; iterative avoids recursion overhead, while STL-based merges are simpler but may use more memory.

Approach	Time	Space	Best For
Recursive Merge Sort	O(n log n)	O(n)	General purpose, easy to understand
Iterative Merge Sort	O(n log n)	O(n)	Avoid recursion, stack-safe
STL Vector with std::merge	O(n log n)	O(n)	Cleaner code, uses C++ standard library