Merge Sort in C++
What is Merge Sort in C++?
Merge sort is one the sorting technique that is used to sort the data in a logical order. It uses divide and conquer approach for sorting the data. Merge sort repeatedly breaks down a list into several sub lists until each sub list consists of a single element and merging those sub lists in a manner that results into a sorted list. In this article, we will read more about merge sort in C++.
| Time Complexity | Θ(n Log n) |
| Best Case | Ω(n Log n) |
| Worst Case | O(n Log n) |
| Space Complexity | O(n) |
Merge Sort in C++
- A file of any size can be sorted using merge sort.
- Elements in the merge sort are divided into two sub list again and again until each sub-list contain only one element.
- After this, the elements are merged to make a sorted list.
- It requires more space and is less efficient
Execution of Merge sort in C++
Merge sort is executed in three steps:-
1.) Divide Step:
First of all the array will be divide in to N sub list, until each sub list contains only one element.
2.) Conquer Step:
Take two sub list and place them in logical order.
3.) Combine Step:
Combine the elements back by merging the two sorted sub list into a sorted sequence.
Program for merge sort in C++
We will look at two different methods, both have the same time complexity with the difference that –
- Method 1 – Uses two temp subarrays
- Method 2 – Uses 1 temp subarray
The combined size of two temp subarrays in method 1 is the same as the whole array in method 2. So the space complexity remains the same.
#include<iostream>
using namespace std;
void mergeSort(int[],int,int);
void merge(int[],int,int,int);
void printArray(int arr[], int size){
int i;
for(i = 0; i < size; i++){
cout << arr[i] << " ";
}
cout << endl;
}
int main()
{
int array[]= {8, 4, 5, 1, 3, 9, 0, 2, 7, 6};
int i;
int size = sizeof(array)/sizeof(array[0]);
printArray(array, size);
mergeSort(array, 0, size-1);
printArray(array, size);
}
void mergeSort(int a[], int left, int right)
{
int mid;
if(left < right)
{
// can also use mid = left + (right - left) / 2
// this can avoid data type overflow
mid = (left + right)/2;
// recursive calls to sort first half and second half subarrays
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
}
void merge(int arr[], int left, int mid, int right)
{
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
// create temp arrays to store left and right subarrays
int L[n1], R[n2];
// Copying data to temp arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// here we merge the temp arrays back into arr[l..r]
i = 0; // Starting index of L[i]
j = 0; // Starting index of R[i]
k = left; // Starting index of merged subarray
while (i < n1 && j < n2)
{
// place the smaller item at arr[k] pos
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[], if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}Output
8 4 5 1 3 9 0 2 7 6 0 1 2 3 4 5 6 7 8 9
#include<iostream>
using namespace std;
void mergeSort(int[],int,int);
void merge(int[],int,int,int);
void printArray(int arr[], int size){
int i;
for(i = 0; i < size; i++){
cout << arr[i] << " ";
}
cout << endl;
}
int main()
{
int array[]= {8, 4, 5, 1, 3, 9, 0, 2, 7, 6};
int i;
int size = sizeof(array)/sizeof(array[0]);
printArray(array, size);
mergeSort(array, 0, size-1);
printArray(array, size);
}
void mergeSort(int a[], int left, int right)
{
int mid;
if(left < right)
{
// can also use mid = left + (right - left) / 2
// this can avoid data type overflow
mid = (left + right)/2;
// recursive calls to sort first half and second half subarrays
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
}
void merge(int a[], int left, int mid, int right)
{
int i = left; // starting index of left subarray
int j = mid + 1; // starting index of right subarray
int index = left; // used to place items in temp[]
int temp[10];
while(i<=mid && j<=right)
{
// place the smaller item at temp[index]
if(a[i] < a[j]) { temp[index] = a[i]; i = i+1; } else { temp[index] = a[j]; j = j+1; } index++; } // i > mid would mean all items for left
// subarray were successfully placed, and there
// must be unplaced right subarray items
if(i>mid)
{
while(j<=right)
{
temp[index] = a[j];
index++;
j++;
}
}
// else all items of right subarray must have
// been placed and there must be
// unplaced items in the left-subarray
else
{
while(i<=mid)
{
temp[index] = a[i];
index++;
i++;
}
}
int p = left; // left index of subarray
// by now index would have reached right
// most index of right subarray
// placing all items of temp[] into actual array a[]
while(p < index)
{
a[p]=temp[p];
p++;
}
}Output
8 4 5 1 3 9 0 2 7 6 0 1 2 3 4 5 6 7 8 9
Performance
Strengths
- With a good time complexity of O(n log n), merge sort is great !!!
- Good to learn Divide and conquer algorithm later used in Dynamic Programming concepts
Weakness
- Poor space complexity of O(n)
- Lots of overhead in copying data between arrays and making new arrays
Fun Fact
Merge Sort is useful for sorting linked lists. Merge Sort is a stable sort which means that the same element in an array maintain their original positions with respect to each other. Overall time complexity of Merge sort is O(nLogn).
Login/Signup to comment
what is p,q,r?
Hey Rahul, we have taken these three variables, to denote the starting and ending point of the two sub arrays