Published: February 18, 2025 | Reading Time: 5 minutes
Data structures rely on sorting algorithms that organise information effectively. Merge sort in C++ stands out by splitting complex tasks into smaller, manageable parts. The algorithm is based on the principle of the Divide and Conquer strategy and makes data handling easier or faster in many cases. This guide explains the merge sort implementation in C++ with examples and practical uses.
A divide-and-conquer approach solves big problems by splitting them into smaller parts. The method makes each small task simple before putting solutions back together.
A merge sort algorithm splits information into two halves and puts them back in order. It works by:
The process shows excellent results with big data sets because it maintains O(n log n) time complexity. Many applications prefer merge sort for this reason.
MERGE_SORT(arr, start, end)
if start < end
set mid = (start + end) / 2
MERGE_SORT(arr, start, mid)
MERGE_SORT(arr, mid + 1, end)
MERGE(arr, start, mid, end)
end of if
END MERGE_SORT
To understand the merge sort C++ program, let's examine the step-by-step process:
Merge sort starts by dividing the array into two halves.
Next, each of these halves is divided again into smaller parts. We divide the left half into two arrays of size 2.
Finally, we merge the two sorted halves.
| Complexity Type | Value |
|---|---|
| Time Complexity (Best Case) | O(n log n) |
| Time Complexity (Average Case) | O(n log n) |
| Time Complexity (Worst Case) | O(n log n) |
| Space Complexity | O(n) |
Note: Space complexity is O(n) due to the additional space required for merging.
Implementing merge sort C++ code typically involves defining a merge function combining two sorted arrays and a mergeSort function recursively sorts the array.
void merge(int arr[], int left, int mid, int right) {
// Code to merge two halves
}
void mergeSort(int arr[], int left, int right) {
// Code to divide and conquer
}
Key Functions:
Algorithm Components:
arr[]: The main arrayleft: The starting index of the subarray to be sortedright: The ending index of the subarray to be sorted#include <iostream>
using namespace std;
// Function to merge two sorted subarrays
void Merge(int arr[], int left, int mid, int right) {
// Calculate the sizes of the two subarrays
int n1 = mid - left + 1; // Size of left subarray
int n2 = right - mid; // Size of right subarray
// Create temporary arrays for left and right subarrays
int* L = new int[n1]; // Left subarray
int* R = new int[n2]; // Right subarray
// Copy data to temporary arrays L[] and R[]
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 the temporary arrays back into arr[left..right]
int i = 0; // Initial index of first subarray
int j = 0; // Initial index of second subarray
int k = left; // Initial index of merged array
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++;
}
// Free dynamically allocated memory
delete[] L;
delete[] R;
}
// Function to implement merge sort
void MergeSort(int arr[], int left, int right) {
if (left < right) {
// Find the middle point
int mid = left + (right - left) / 2;
// Recursively sort first and second halves
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
// Merge the sorted halves
Merge(arr, left, mid, right);
}
}
// Main function to execute the program
int main() {
// Example array to be sorted
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]); // Calculate number of elements
cout << "Original Array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
MergeSort(arr, 0, n - 1); // Call merge sort on the array
cout << "Sorted Array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
Original Array: 38 27 43 3 9 82 10
Sorted Array: 3 9 10 27 38 43 82
The recurrence relation for Merge Sort is a mathematical expression that describes the algorithm's time complexity in terms of the input size. The relation can be derived based on the algorithm's divide-and-conquer approach.
The recurrence relation for Merge Sort can be expressed as:
T(n) = { Θ(1) if n=1
{ 2T(n/2) + Θ(n) if n>1
Explanation of each element:
Merge Sort is an efficient sorting algorithm with an O(n log n) time complexity. It can be implemented in two ways: Recursive Merge Sort and Iterative Merge Sort.
Recursive Merge Sort follows a divide-and-conquer approach, where the array is recursively split into two halves, each half is sorted, and then the two halves are merged back into a sorted array. The recursion continues until each subarray contains a single element (which is trivially sorted), and then the merge process begins.
#include <iostream>
using namespace std;
// Merge two sorted subarrays
void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
int i = 0, j = 0, k = 0;
while (i < leftSize && j < rightSize) {
arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
}
while (i < leftSize) arr[k++] = left[i++];
while (j < rightSize) arr[k++] = right[j++];
}
// Recursive Merge Sort function
void recursiveMergeSort(int arr[], int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
recursiveMergeSort(arr, left, mid); // Sort left half
recursiveMergeSort(arr, mid + 1, right); // Sort right half
int leftArr[mid - left + 1], rightArr[right - mid];
for (int i = 0; i <= mid - left; i++) leftArr[i] = arr[left + i];
for (int i = 0; i < right - mid; i++) rightArr[i] = arr[mid + 1 + i];
merge(arr, leftArr, mid - left + 1, rightArr, right - mid); // Merge
}
// Driver code to test
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < size; i++) cout << arr[i] << " ";
cout << endl;
recursiveMergeSort(arr, 0, size - 1);
cout << "Sorted array: ";
for (int i = 0; i < size; i++) cout << arr[i] << " ";
cout << endl;
return 0;
}
Original array: 38 27 43 3 9 82 10
Sorted array: 9 9 10 82 3 82 10
While Recursive Merge Sort divides and conquers the problem by calling itself recursively, Iterative Merge Sort does the same task without recursion. Instead, it progressively merges pairs of adjacent elements or subarrays in a bottom-up manner.
#include <iostream>
#include <vector>
using namespace std;
// Merge two sorted subarrays
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> leftArr(arr.begin() + left, arr.begin() + mid + 1);
vector<int> rightArr(arr.begin() + mid + 1, arr.begin() + right + 1);
int i = 0, j = 0, k = left;
while (i < leftArr.size() && j < rightArr.size()) {
arr[k++] = (leftArr[i] <= rightArr[j]) ? leftArr[i++] : rightArr[j++];
}
while (i < leftArr.size()) arr[k++] = leftArr[i++];
while (j < rightArr.size()) arr[k++] = rightArr[j++];
}
// Iterative Merge Sort
void iterativeMergeSort(vector<int>& arr) {
int n = arr.size();
for (int currSize = 1; currSize < n; currSize *= 2) {
for (int left = 0; left < n; left += 2 * currSize) {
int mid = min(left + currSize - 1, n - 1);
int right = min(left + 2 * currSize - 1, n - 1);
merge(arr, left, mid, right);
}
}
}
// Driver code
int main() {
vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
cout << "Original array: ";
for (int i : arr) cout << i << " ";
cout << endl;
iterativeMergeSort(arr);
cout << "Sorted array: ";
for (int i : arr) cout << i << " ";
cout << endl;
return 0;
}
Original array: 38 27 43 3 9 82 10
Sorted array: 3 9 10 27 38 43 82
Linked Lists: Merge sort is particularly well-suited for linked lists because it does not require random access to elements. This makes it ideal when you need to merge two sorted arrays in C++, as the linked list structure allows easy splitting and merging without the need for random access.
External Sorting: It is used in external sorting algorithms where data to be sorted does not fit into memory, as it efficiently handles large datasets by dividing them into smaller chunks.
Stable Sorting: Merge sort maintains the relative order of equal elements, making it ideal for sorting data structures where stability is essential, such as sorting records in databases.
Parallel Processing: The divide-and-conquer approach allows for easy parallelisation, making it suitable for multi-threaded applications.
Consistent Performance: Merge sort has a consistent time complexity of O(n log n) for best, average, and worst cases, making it efficient for large datasets.
Stability: It is a stable sorting algorithm, preserving the relative order of equal elements.
Predictable Performance: Compared to quicksort, which can degrade to O(n²) in the worst case, merge sort guarantees O(n log n) performance regardless of input.
Works Well with Linked Lists: It can be implemented without extra space when sorting linked lists, as merging can be done in place.
Space Complexity: Merge sort requires additional space proportional to the size of the input array (O(n)), which can be a drawback for large datasets.
Overhead: The recursive nature and merging process introduce overhead compared to simpler algorithms like insertion or selection sort for small datasets.
Not In-Place: The standard implementation is not an in-place algorithm since it requires extra storage for temporary arrays.
Here are coding questions with C++ code asked in top companies' assessments on merge sort:
Problem Statement: Given an array, count the number of inversions in the array. An inversion is a pair of indices (i, j) such that i < j and arr[i] > arr[j].
Sample Input:
5
2, 3, 8, 6, 1
Output:
5
#include <iostream>
using namespace std;
int mergeAndCount(int arr[], int left, int mid, int right) {
int i = left; // Starting index for left subarray
int j = mid + 1; // Starting index for right subarray
int k = left; // Starting index to be sorted
int inv_count = 0;
// Create a temporary array
int temp[right + 1];
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
inv_count += (mid - i + 1); // Count inversions
}
}
// Copy remaining elements of left subarray
while (i <= mid) {
temp[k++] = arr[i++];
}
// Copy remaining elements of right subarray
while (j <= right) {
temp[k++] = arr[j++];
}
// Copy sorted subarray into Original array
for (int i = left; i <= right; i++) {
arr[i] = temp[i];
}
return inv_count;
}
int mergeSortAndCount(int arr[], int left, int right) {
int inv_count = 0;
if (left < right) {
int mid = left + (right - left) / 2;
inv_count += mergeSortAndCount(arr, left, mid);
inv_count += mergeSortAndCount(arr, mid + 1, right);
inv_count += mergeAndCount(arr, left, mid, right);
}
return inv_count;
}
int main() {
int n;
cout << "Enter the number of elements in the array: ";
cin >> n;
int* arr = new int[n]; // Dynamically allocate array
cout << "Enter the elements of the array:\n";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Number of inversions:" << mergeSortAndCount(arr, 0, n - 1) << endl;
delete[] arr; // Free dynamically allocated memory
return 0;
}
Enter the number of elements in the array: 5
Enter the elements of the array:
2 3 8 6 1
Number of inversions: 5
Problem Statement: Given k sorted arrays of different sizes, merge them into a single sorted array.
Sample Input:
arr1 = [1, 4, 7]
arr2 = [2, 5]
arr3 = [3, 6]
Output:
[1, 2, 3, 4, 5, 6, 7]
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Element {
int value;
int arrayIndex;
int elementIndex;
bool operator>(const Element& other) const {
return value > other.value; // Min-heap based on value
}
};
vector<int> mergeKSortedArrays(vector<vector<int>>& arrays) {
priority_queue<Element, vector<Element>, greater<Element>> minHeap;
// Initialize the heap with the first element of each array
for (int i = 0; i < arrays.size(); i++) {
if (!arrays[i].empty()) {
minHeap.push({arrays[i][0], i, 0});
}
}
vector<int> mergedArray;
while (!minHeap.empty()) {
Element current = minHeap.top();
minHeap.pop();
mergedArray.push_back(current.value);
// If there is a next element in the same array
if (current.elementIndex + 1 < arrays[current.arrayIndex].size()) {
minHeap.push({arrays[current.arrayIndex][current.elementIndex + 1], current.arrayIndex,
current.elementIndex + 1});
}
}
return mergedArray;
}
int main() {
int k;
cout << "Enter number of sorted arrays: ";
cin >> k;
vector<vector<int>> arrays(k);
for (int i = 0; i < k; i++) {
int n;
cout << "Enter number of elements in array " << (i + 1) << ": ";
cin >> n;
cout << "Enter elements of array " << (i + 1) << ": ";
arrays[i].resize(n);
for (int j = 0; j < n; j++) {
cin >> arrays[i][j];
}
}
vector<int> result = mergeKSortedArrays(arrays);
cout << "Merged Array: ";
for (int num : result) {
cout << num << " ";
}
cout << endl;
return 0;
}
Enter number of sorted arrays: 3
Enter number of elements in array 1: 3
Enter elements of array 1: 1 4 7
Enter number of elements in array 2: 2
Enter elements of array 2: 2 5
Enter number of elements in array 3: 2
Enter elements of array 3: 3 6
Merged Array: 1 2 3 4 5 6 7
Problem Statement: Given two sorted arrays A[] and B[] of sizes N and M, the task is to merge both arrays into a single array in non-decreasing order.
Sample Input:
3
1 3 5
3
2 4 6
Output:
1 2 3 4 5 6
#include <iostream>
using namespace std;
void mergeArrays(int arr1[], int arr2[], int n1, int n2, int arr3[]) {
int i = 0, j = 0, k = 0;
// Merge both arrays
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j]) {
arr3[k++] = arr1[i++];
} else {
arr3[k++] = arr2[j++];
}
}
// Copy remaining elements from arr1[]
while (i < n1) {
arr3[k++] = arr1[i++];
}
// Copy remaining elements from arr2[]
while (j < n2) {
arr3[k++] = arr2[j++];
}
}
int main() {
int n1, n2;
// Input for the first sorted array
cout << "Enter the number of elements in the first sorted array: ";
cin >> n1;
int* arr1 = new int[n1]; // Dynamically allocate memory for the first array
cout << "Enter elements of the first sorted array:\n";
for (int i = 0; i < n1; i++) {
cin >> arr1[i];
}
// Input for the second sorted array
cout << "Enter the number of elements in the second sorted array: ";
cin >> n2;
int* arr2 = new int[n2]; // Dynamically allocate memory for the second array
cout << "Enter elements of the second sorted array:\n";
for (int i = 0; i < n2; i++) {
cin >> arr2[i];
}
// Merged array
int* mergedArray = new int[n1 + n2];
// Merge the two arrays
mergeArrays(arr1, arr2, n1, n2, mergedArray);
// Output the merged array
cout << "Merged Array: ";
for (int i = 0; i < n1 + n2; i++) {
cout << mergedArray[i] << " ";
}
cout << endl;
// Free dynamically allocated memory
delete[] arr1;
delete[] arr2;
delete[] mergedArray;
return 0;
}
Enter the number of elements in the first sorted array: 3
Enter elements of the first sorted array:
1 3 5
Enter the number of elements in the second sorted array: 3
Enter elements of the second sorted array:
2 4 6
Merged Array: 1 2 3 4 5 6
In conclusion, merge sort C++ is an efficient and stable sorting algorithm that uses the divide-and-conquer strategy, achieving a time complexity of O(n log n). It is mainly used in handling large datasets and maintains the relative order of equal elements, making it ideal for applications requiring stability. While it is particularly effective for sorting linked lists and external data, its requirement for additional memory can be a drawback in memory-constrained environments. Merge Sort's predictable performance and versatility make it a valuable tool in C++ programming, suitable for various applications where efficient sorting is essential.
The time complexity of Merge Sort Program in C++:
Yes, Merge Sort is very efficient for linked lists because linked lists allow easy splitting and merging operations. When sorting linked lists, you don't need extra space for arrays as in the case of arrays, and Merge Sort can be implemented in O(n log n) time with O(1) extra space.
Options:
a) O(n)
b) O(n log n)
c) O(log n)
d) O(n^2)
Answer: b) O(n log n)
Options:
a) Divide and Conquer
b) Greedy Algorithm
c) Dynamic Programming
d) Backtracking
Answer: a) Divide and Conquer
Options:
a) O(1)
b) O(n)
c) O(log n)
d) O(n^2)
Answer: b) O(n)
Options:
a) O(n)
b) O(n log n)
c) O(log n)
d) O(n^2)
Answer: b) O(n log n)
Ultimate Guide to Function Overloading in C++ - Learn Function Overloading in C++ with clear examples, rules, use cases, differences from overriding, and best practices for efficient coding.
Learn Multiset in C++: Properties and Key Functions - Discover the properties and key functions of the multiset in C++. Learn about its sorted order, duplicate handling, and functions like insert, erase, and find.
Understanding Multiset, Unordered Sets and Bit Sets in C++ - Discover multiset, unordered sets and bit sets in C++ with the set's common properties and functions for efficient data handling.
Message Passing in C++: Working & Implementation - Message passing in C++ is for object communication. Learn key concepts, methods, and practical examples to implement in your programs.
What are the Key Benefits of OOP in C++? - The benefits of oop in c++ enhance code modularity, reusability, maintainability, and scalability, leading to better organization, security, and productivity in software development.
Dynamic Constructors in C++: Implementation & Examples - Learn how dynamic constructors in C++ enable runtime object creation, dynamic initialisation, and memory allocation for more flexible and efficient programs.
About NxtWave
NxtWave provides industry-recognized certifications and training programs for students and professionals looking to advance their careers in technology. Contact us for more information about our courses and programs.
Contact Information:
Course Offerings: