Merge Sort in C++

Merge Sort Algorithm in C++ (Complete Implementation).

IntermediateSorting & Searching ProgramsExample 4 of 13

merge-sort.cpp

1#include <iostream>
2using namespace std;
3
4void merge(int arr[], int left, int mid, int right) {
5    int n1 = mid - left + 1;
6    int n2 = right - mid;
7    
8    // Create temporary arrays
9    int L[n1], R[n2];
10    
11    // Copy data to temp arrays
12    for (int i = 0; i < n1; i++)
13        L[i] = arr[left + i];
14    for (int j = 0; j < n2; j++)
15        R[j] = arr[mid + 1 + j];
16    
17    // Merge temp arrays back
18    int i = 0, j = 0, k = left;
19    while (i < n1 && j < n2) {
20        if (L[i] <= R[j]) {
21            arr[k] = L[i];
22            i++;
23        } else {
24            arr[k] = R[j];
25            j++;
26        }
27        k++;
28    }
29    
30    // Copy remaining elements
31    while (i < n1) {
32        arr[k] = L[i];
33        i++;
34        k++;
35    }
36    while (j < n2) {
37        arr[k] = R[j];
38        j++;
39        k++;
40    }
41}
42
43void mergeSort(int arr[], int left, int right) {
44    if (left < right) {
45        int mid = left + (right - left) / 2;
46        
47        // Sort first and second halves
48        mergeSort(arr, left, mid);
49        mergeSort(arr, mid + 1, right);
50        
51        // Merge sorted halves
52        merge(arr, left, mid, right);
53    }
54}
55
56void printArray(int arr[], int n) {
57    for (int i = 0; i < n; i++) {
58        cout << arr[i] << " ";
59    }
60    cout << endl;
61}
62
63int main() {
64    int arr[] = {64, 34, 25, 12, 22, 11, 90};
65    int n = sizeof(arr) / sizeof(arr[0]);
66    
67    cout << "Original array: ";
68    printArray(arr, n);
69    
70    mergeSort(arr, 0, n - 1);
71    
72    cout << "Sorted array: ";
73    printArray(arr, n);
74    
75    return 0;
76}

Output

Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

What's going on

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.

Header File Used

This header provides:

cout for displaying output

cin for taking input from the user

1#include <iostream>

Understanding Merge Sort

Divide-and-Conquer Strategy

Divide

: Split array into two halves

Conquer

: Recursively sort both halves

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]

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

}

1// 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

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

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]

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)

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

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

return 0;

This ends the program successfully.

PreviousSelection Sort NextQuick Sort