Table of contents  
Introduction  
Understanding the Merge Sort Algorithm  
Implementation of Merge Sort in C++  
Explanation of the Code  
Sample Problems  
Conclusion 
Merge sort is a popular and efficient sorting algorithm that falls under the category of divide and conquer algorithms. It is often considered one of the best sorting algorithms due to its stability, predictable performance, and relatively simple implementation. In this article, we will explore how to implement the merge sort algorithm in C++.
The merge sort algorithm follows a divide and conquer approach, which means it breaks down the problem into smaller subproblems until they become simple enough to solve. The basic steps of the merge sort algorithm are as follows:
Let's now look at the C++ implementation of the merge sort algorithm. We will start by defining a function 'mergeSort()' that takes an array, its leftmost index, and its rightmost index as parameters.
#include <iostream>
using namespace std;
void merge(int arr[], int left, int middle, int right) {
int i, j, k;
int n1 = middle  left + 1;
int n2 = right  middle;
// Create temporary arrays
int L[n1], R[n2];
// Copy data to temporary arrays
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[middle + 1 + j];
// Merge the temporary arrays back into arr[l..r]
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 the remaining elements of L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
// Find the middle point
int middle = left + (right  left) / 2;
// Sort first and second halves
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
// Merge the sorted halves
merge(arr, left, middle, right);
}
}
int main() {
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arrSize = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < arrSize; i++)
cout << arr[i] << " ";
cout << endl;
mergeSort(arr, 0, arrSize  1);
cout << "Sorted array: ";
for (int i = 0; i < arrSize; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
In this code snippet, we first define the 'merge()' function, which is responsible for merging two sorted subarrays into one. Then, we define the 'mergeSort()' function, which recursively divides the array into smaller subarrays and performs the merge operation.
Running the above code will produce the following output:
Original array: 12 11 13 5 6 7
Sorted array: 5 6 7 11 12 13
Problem: Sort the following array using merge sort: '{ 7, 2, 9, 1, 6, 5 }'. Output the sorted array.
After applying merge sort, the sorted array will be: '{ 1, 2, 5, 6, 7, 9 }'.
Problem: Sort the following array in descending order using merge sort: { 3, 8, 1, 4, 6, 2 }. Output the sorted array.
By modifying the comparison condition in the merge() function to L[i] >= R[j], the sorted array in descending order will be: { 8, 6, 4, 3, 2, 1 }.
Problem: What is the time complexity of the merge sort algorithm?
The time complexity of merge sort is O(n log n), where n is the number of elements in the array. This makes it an efficient sorting algorithm for large datasets.
In this article, we explored the merge sort algorithm and its implementation in C++. We learned how merge sort follows a divide and conquer approach to efficiently sort an array. By understanding the code and examples provided, you should now have a solid foundation in implementing merge sort in C++.
70 videos45 docs15 tests

70 videos45 docs15 tests


Explore Courses for Software Development exam
