Merge Sort is a classic and highly efficient sorting algorithm that uses the divide-and-conquer technique to sort elements. This algorithm is notable for its predictable performance and stability, making it a popular choice for sorting large datasets. This article will guide you through the implementation of Merge Sort in C++, providing detailed explanations and examples to illustrate its application.
Prerequisites
Before diving into the implementation, ensure you have a basic understanding of the following concepts:
- Arrays: A collection of elements stored at contiguous memory locations.
- C++ Syntax: Basic knowledge of C++ programming, including loops, conditional statements, and functions.
- Recursion: Understanding how recursive functions work, as Merge Sort is implemented using recursion.
1. Introduction to Merge Sort
1.1 Definition
Merge Sort is an efficient, stable, comparison-based, divide-and-conquer sorting algorithm. It works by recursively splitting the array into halves until each sub-array contains a single element, then merging these sub-arrays in a sorted manner.
1.2 Algorithm Steps
- Divide: Split the array into two halves.
- Conquer: Recursively sort each half.
- Merge: Merge the two sorted halves to produce the sorted array.
2. Implementation of Merge Sort in C++
2.1 Example 1: Basic Merge Sort
Let’s start with a basic implementation of Merge Sort in C++.
#include <iostream>
using namespace std;
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int leftArray[n1], rightArray[n2];
for (int i = 0; i < n1; i++)
leftArray[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArray[j] = arr[mid + 1 + j];
int i = 0;
int j = 0;
int k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArray[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArray[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) {
if (left >= right)
return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
cout << "Given array is \n";
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
cout << "\nSorted array is \n";
printArray(arr, arr_size);
return 0;
}
Output:
Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
2.2 Example 2: Merge Sort with Larger Array
Here is another example with a larger array to show how Merge Sort handles more data.
#include <iostream>
using namespace std;
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int leftArray[n1], rightArray[n2];
for (int i = 0; i < n1; i++)
leftArray[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArray[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArray[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArray[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) {
if (left >= right)
return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
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, 22, 17, 5, 15, 6};
int arr_size = sizeof(arr) / sizeof(arr[0]);
cout << "Given array is \n";
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
cout << "\nSorted array is \n";
printArray(arr, arr_size);
return 0;
}
Output:
Given array is
38 27 43 3 9 82 10 22 17 5 15 6
Sorted array is
3 5 6 9 10 15 17 22 27 38 43 82
2.3 Example 3: Merge Sort with Strings
Merge Sort can also be applied to an array of strings. This example demonstrates sorting an array of strings in lexicographical order.
#include <iostream>
#include <string>
using namespace std;
void merge(string arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
string leftArray[n1], rightArray[n2];
for (int i = 0; i < n1; i++)
leftArray[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArray[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArray[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArray[j];
j++;
k++;
}
}
void mergeSort(string arr[], int left, int right) {
if (left >= right)
return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
void printArray(string arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
string arr[] = {"apple", "orange", "banana", "grape", "cherry"};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Given array is \n";
printArray(arr, n);
mergeSort(arr, 0, n - 1);
cout << "\nSorted array is \n";
printArray(arr, n);
return 0;
}
Output:
Given array is
apple orange banana grape cherry
Sorted array is
apple banana cherry grape orange
Conclusion
Merge Sort is a robust and reliable sorting algorithm with a time complexity of O(n log n) in all cases (worst, average, and best). It is particularly useful for sorting large datasets and is stable, meaning it maintains the relative order of equal elements. This article provided a comprehensive guide to implementing Merge Sort in C++, demonstrating its application through examples with integers and strings.