Merge Sort in C++: Algorithm, Code, and Everything You Need to Know

Merge sort is one of those algorithms that every C++ programmer should know about it. It is fast, reliable, and built on a concept called divide and conquer, where you break a big problem into smaller ones, solve each part, and combine the results. Whether you are sorting a list of names, exam scores, or millions of records, merge sort handles it efficiently.

In this blog, you will learn exactly how merge sort works, see a complete merge sort C++ program with a line-by-line walkthrough, understand its time and space complexity, compare it with other sorting methods, and know when to actually use it. By the end, you will be comfortable writing merge sort code from scratch.

Ready to go beyond algorithms and start building real-world AI solutions? Explore upGrad’s Artificial Intelligence Courses to learn machine learning, generative AI, and cutting-edge technologies through hands-on projects and practical applications.

How Merge Sort Works in C++

Merge sort follows a three-step process: divide, conquer, and merge.

Here is the simple version of what happens:

1. Split the array into two halves.
2. Recursively sort each half.
3. Merge both sorted halves into one sorted array.

This keeps repeating until every sub-array has just one element. A single-element array is already sorted by definition. Then the merge step builds the final sorted result.

Visual Example

Key Idea

The merge step is the heart of the algorithm. Dividing is just preparation. The real work is in merging two already-sorted arrays into one.

Merge Sort C++ Code (Full Program)

Here is a complete, working merge sort C++ program. Read through the comments as you go.

#include <iostream>
using namespace std;

// Merges two sorted subarrays: arr[left..mid] and arr[mid+1..right]
void merge(int arr[], int left, int mid, int right) {
   int n1 = mid - left + 1;  // Size of left subarray
   int n2 = right - mid;     // Size of right subarray

   // Temporary arrays
   int L[n1], R[n2];

   // Copy data into 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];

   int i = 0, j = 0, k = left;

   // Merge L and R back into arr
   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 of L, if any
   while (i < n1) {
       arr[k] = L[i];
       i++; k++;
   }

   // Copy remaining elements of R, if any
   while (j < n2) {
       arr[k] = R[j];
       j++; k++;
   }
}

// Main merge sort function
void mergeSort(int arr[], int left, int right) {
   if (left < right) {
       int mid = left + (right - left) / 2; // Avoid overflow

       mergeSort(arr, left, mid);       // Sort left half
       mergeSort(arr, mid + 1, right);  // Sort right half
       merge(arr, left, mid, right);    // Merge both halves
   }
}

// Utility function to print array
void printArray(int arr[], int size) {
   for (int i = 0; i < size; i++)
       cout << arr[i] << " ";
   cout << endl;
}

int main() {
   int arr[] = {38, 27, 43, 3, 9, 82, 10};
   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: 38 27 43 3 9 82 10
Sorted array:   3 9 10 27 38 43 82
 

Code Breakdown

Function	Purpose
mergeSort()	Recursively divides the array
merge()	Compares and merges two sorted halves
printArray()	Displays the array

The mid = left + (right - left) / 2 formula is used instead of (left + right) / 2 to avoid integer overflow when left and right are large numbers. This is a common trick used in production code.

Also Read: Data Structures and Algorithms (DSA)

Time and Space Complexity of Merge Sort

Understanding complexity helps you decide when merge sort is the right tool. Here is a quick breakdown:

Time Complexity

Case	Time Complexity	When It Happens
Best Case	O(n log n)	Array is already sorted
Average Case	O(n log n)	Random order
Worst Case	O(n log n)	Array is in reverse order

This is what makes merge sort special. Unlike quicksort, merge sort always runs in O(n log n) regardless of input order. There are no bad cases.

Space Complexity

Type	Complexity
Auxiliary Space	O(n)

Merge sort needs extra memory to store temporary arrays during the merge step. This is its main drawback. For very large datasets where memory is tight, this matters.

Why O(n log n)?

The array is split log n times (since you keep halving). At each level of splitting, you do O(n) work during merging. Multiply them and you get O(n log n).

Merge Sort vs Other Sorting Algorithms

Knowing when to use merge sort means understanding where it stands against other options.

Algorithm	Best Case	Average Case	Worst Case	Stable	In-Place
Merge Sort	O(n log n)	O(n log n)	O(n log n)	Yes	No
Quick Sort	O(n log n)	O(n log n)	O(n²)	No	Yes
Bubble Sort	O(n)	O(n²)	O(n²)	Yes	Yes
Insertion Sort	O(n)	O(n²)	O(n²)	Yes	Yes
Heap Sort	O(n log n)	O(n log n)	O(n log n)	No	Yes

What "Stable" Means

A stable sort keeps equal elements in their original order. If two students have the same score, stable sort preserves who came first. Merge sort is stable. Quicksort and heap sort are not.

When to Choose Merge Sort

Use merge sort when:

• You need guaranteed O(n log n) in all cases
• Stability matters (sorting objects with multiple fields)
• You are sorting linked lists (merge sort works better than quicksort on linked lists)
• External sorting (data too large to fit in RAM)

Avoid merge sort when:

• Memory is very limited (due to O(n) extra space)
• You want an in-place sort
• Data is small (insertion sort often wins for tiny arrays)

Also Read: Insertion Sort Algorithm in Data Structures

Merge Sort for Linked Lists in C++

Merge sort is actually the preferred algorithm for sorting linked lists. Here is why: linked lists do not support random access, so algorithms like quicksort that rely on index-based swaps perform poorly. Merge sort only needs sequential access and pointer manipulation, making it a natural fit.

Approach

The logic is similar but adapted for nodes:

1. Use the slow and fast pointer technique to find the middle of the list.
2. Split the list into two halves.
3. Recursively sort each half.
4. Merge the two sorted halves by comparing node values.

#include <iostream>
using namespace std;

struct Node {
   int data;
   Node* next;
   Node(int val) : data(val), next(nullptr) {}
};

// Split list into two halves
void splitList(Node* head, Node** left, Node** right) {
   Node* slow = head;
   Node* fast = head->next;

   while (fast != nullptr && fast->next != nullptr) {
       slow = slow->next;
       fast = fast->next->next;
   }

   *left = head;
   *right = slow->next;
   slow->next = nullptr;
}

// Merge two sorted linked lists
Node* mergeSorted(Node* a, Node* b) {
   if (!a) return b;
   if (!b) return a;

   if (a->data <= b->data) {
       a->next = mergeSorted(a->next, b);
       return a;
   } else {
       b->next = mergeSorted(a, b->next);
       return b;
   }
}

// Merge sort for linked list
void mergeSort(Node** head) {
   if (*head == nullptr || (*head)->next == nullptr) return;

   Node* left;
   Node* right;

   splitList(*head, &left, &right);
   mergeSort(&left);
   mergeSort(&right);
   *head = mergeSorted(left, right);
}

void printList(Node* head) {
   while (head) {
       cout << head->data << " ";
       head = head->next;
   }
   cout << endl;
}

int main() {
   Node* head = new Node(5);
   head->next = new Node(2);
   head->next->next = new Node(8);
   head->next->next->next = new Node(1);
   head->next->next->next->next = new Node(4);

   cout << "Original: ";
   printList(head);

   mergeSort(&head);

   cout << "Sorted:  ";
   printList(head);

   return 0;
}
 

Output:

Original: 5 2 8 1 4
Sorted:   1 2 4 5 8
 

Key Points

• splitList() uses slow/fast pointers to find the midpoint in O(n) time
• mergeSorted() merges two sorted lists recursively by adjusting next pointers
• No extra array memory is needed here since you reuse existing nodes
• This version of merge sort program in C++ is O(n log n) in time and O(log n) in space (stack space for recursion)

Also Read: Understanding While Loop in Python with Examples

Common Mistakes to Avoid in Merge Sort C++ Programs

Even experienced programmers trip up here. Watch out for these:

1. Using (left + right) / 2 for mid calculation This causes integer overflow with large indices. Always use left + (right - left) / 2.

2. Off-by-one errors in index ranges The left subarray is arr[left..mid] and the right is arr[mid+1..right]. Getting these boundaries wrong silently corrupts results.

3. Forgetting to copy remaining elements After the main merge loop, one subarray might still have elements left. You need those two while loops at the end to copy them over.

4. Not accounting for extra memory If you are solving a memory-constrained problem, merge sort might not be ideal. Always factor in the O(n) auxiliary space.

5. Confusing merge sort with quick sort Both use divide and conquer, but the key difference is: merge sort divides blindly and merges carefully. Quick sort partitions carefully and merges trivially (no actual merge step).

Also Read: Insertion Sort in Java: Explained with Examples

Conclusion

Merge sort is a fundamental algorithm that every serious C++ programmer needs to understand. It gives you guaranteed O(n log n) performance in all cases, it is stable, and it handles edge cases gracefully. Yes, it uses extra memory, but in most real-world scenarios, that trade-off is worth it.

Start by understanding the divide-and-conquer idea. Then study the merge step closely, because that is where the algorithm does its real work. Once you can write the merge sort C++ program from memory and explain why each line is there, you have a real edge in both interviews and production coding.

Want personalized guidance on AI and upskilling? Speak with an expert for a free 1:1 counselling session today.