Merge Sort

Merge Sort Algorithm in C++ (Complete Implementation)

IntermediateTopic: Sorting & Searching Programs
Back

C++ Merge Sort Program

This program helps you to learn the fundamental structure and syntax of C++ programming.

Try This Code
#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // Create temporary arrays
    int L[n1], R[n2];
    
    // Copy data to temp arrays
    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];
    
    // Merge temp arrays back
    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++;
    }
    
    // Copy remaining elements
    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;
        
        // Sort first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        // Merge sorted halves
        merge(arr, left, mid, right);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Original array: ";
    printArray(arr, n);
    
    mergeSort(arr, 0, n - 1);
    
    cout << "Sorted array: ";
    printArray(arr, n);
    
    return 0;
}
Output
Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

Understanding Merge Sort

This program teaches you how to implement the Merge Sort algorithm in C++. Merge Sort is a divide-and-conquer algorithm that divides the array into two halves, recursively sorts them, and then merges the sorted halves. It's one of the most efficient sorting algorithms with guaranteed O(n log n) performance, making it ideal for large datasets.

---

1. What This Program Does

The program sorts an array of integers using the Merge Sort algorithm. For example:

•Input array: [64, 34, 25, 12, 22, 11, 90]
•Output array: [11, 12, 22, 25, 34, 64, 90]
Merge Sort uses a divide-and-conquer approach: it divides the problem into smaller subproblems, solves them recursively, and combines the solutions.

---

2. Header File Used

This header provides:

•cout for displaying output
•cin for taking input from the user

---

#include <iostream>

3. Understanding Merge Sort

Divide-and-Conquer Strategy

:

1.

Divide

: Split array into two halves

2.

Conquer

: Recursively sort both halves

3.

Combine

: Merge the sorted halves

Visual Example

:

[64, 34, 25, 12, 22, 11, 90]

↓ Divide

[64, 34, 25] [12, 22, 11, 90]

↓ Divide ↓ Divide

[64] [34, 25] [12, 22] [11, 90]

↓ Merge ↓ Merge ↓ Merge

[64] [25, 34] [12, 22] [11, 90]

↓ Merge ↓ Merge

[25, 34, 64] [11, 12, 22, 90]

↓ Merge

[11, 12, 22, 25, 34, 64, 90]

---

4. Function: merge()

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

// Merge temp arrays back

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

}

// Copy remaining elements

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

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

}

    // Copy data to temp arrays

How it works

:

•Creates temporary arrays L and R for left and right halves
•Copies elements to temp arrays
•Merges by comparing elements from both arrays
•Copies remaining elements from non-empty array

---

5. Function: mergeSort()

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

}

}

How it works

:

•Base case: if left >= right, subarray has 0 or 1 element (already sorted)
•Divide: calculate mid point
•Conquer: recursively sort left and right halves
•Combine: merge the sorted halves

---

6. Understanding the Merge Process

Merging Two Sorted Arrays

:

Left: [25, 34, 64] Right: [11, 12, 22, 90]

Step 1

: Compare 25 and 11 → 11 is smaller → place 11

Result: [11, ...]

Step 2

: Compare 25 and 12 → 12 is smaller → place 12

Result: [11, 12, ...]

Step 3

: Compare 25 and 22 → 22 is smaller → place 22

Result: [11, 12, 22, ...]

Step 4

: Compare 25 and 90 → 25 is smaller → place 25

Result: [11, 12, 22, 25, ...]

Step 5

: Compare 34 and 90 → 34 is smaller → place 34

Result: [11, 12, 22, 25, 34, ...]

Step 6

: Compare 64 and 90 → 64 is smaller → place 64

Result: [11, 12, 22, 25, 34, 64, ...]

Step 7

: Right array exhausted, copy remaining from left

Result: [11, 12, 22, 25, 34, 64, 90]

---

7. Time and Space Complexity

Time Complexity

: O(n log n) in all cases

•Divide: O(log n) levels of recursion
•Merge: O(n) work at each level
•Total: O(n log n) - consistent performance

Space Complexity

: O(n)

•Requires temporary arrays for merging
•Additional space for recursive calls: O(log n)
•Total: O(n)

Stability

: Stable

•Merge process preserves relative order
•When L[i] == R[j], L[i] is placed first (<= comparison)

---

8. When to Use Merge Sort

Best For

:

•Large datasets
•When stable sorting is required
•When consistent O(n log n) performance is needed
•External sorting (sorting data that doesn't fit in memory)
•Linked lists (efficient merge operation)

Not Recommended For

:

•Small datasets (overhead of recursion and merging)
•When memory is limited (requires O(n) extra space)
•When in-place sorting is required

---

9. Important Considerations

Recursive Nature

:

•Uses recursion to divide problem
•Base case: subarray with 0 or 1 element
•Each recursive call handles smaller subproblem

Temporary Arrays

:

•Requires O(n) extra space
•L and R arrays store halves during merge
•Space trade-off for guaranteed performance

Mid Calculation

:

•mid = left + (right - left) / 2
•Prevents integer overflow
•Better than (left + right) / 2

---

10. return 0;

This ends the program successfully.

---

Summary

•Merge Sort uses divide-and-conquer: divide, conquer (recursively sort), combine (merge).
•Time complexity: O(n log n) in all cases - consistent and reliable.
•Space complexity: O(n) - requires temporary arrays for merging.
•Stable algorithm - preserves relative order of equal elements.
•Guaranteed O(n log n) performance makes it reliable for large datasets.
•Recursive algorithm - divides problem into smaller subproblems.
•Merge process combines two sorted arrays efficiently.
•Understanding Merge Sort is essential for learning efficient sorting algorithms.

This program is fundamental for beginners learning divide-and-conquer algorithms, understanding recursion, and preparing for advanced algorithm design in C++ programs.

Let us now understand every line and the components of the above program.

Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.

Practical Learning Notes for Merge Sort

This C++ program is part of the "Sorting & Searching Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.

A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.

For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.

Next
Quick Sort
Previous
Selection Sort
Next
Quick Sort

Table of Contents