Updated April 18, 2023
Introduction to Merge sort C++
The sorting technique based on the Divide and conquer algorithm is called merge sort, which divides the given input array into two halves and the same merge sort function is called for the divided two halves to sort the two halves that are divided and then merges the sorted two halves into a single sorted array and the function used to sort the each divided array is called mergeSort() function and to merge the two arrays, we make use of another function called merge() function the time complexity for merge sort technique is O(n log n) and space complexity for merge sort technique is O(n). In this topic, we are going to learn about Merge sort C++.
Syntax:
The syntax to define merge() function in C++ is as follows:
merge(input_array, left, middle, right)where input_array is the array of elements that are to be sorted, left indicates the left index in the array, middle indicates the middle index in the array and right indicates the right index in the array.
mergeSort(input_array, left, right)Where input_array is the array of elements that are to be sorted, left indicates the lower bound in the array and right indicates the upper bound in the array.
Working of merge() and mergerSort() function in C++
- The working of merge sort begins by finding the middle point, which divides the given input array into two parts.
- Then we are going to call the mergeSort() function on the first half of the given input array to sort the array.
- Then we are going to call the mergeSort() function on the second half of the given input array to sort the array.
- Then we are going to call the merge() function to merge the two sorted arrays from the second and third steps.
- The merge() function returns a single sorted array.
Examples of Merge sort C++
Here are the following examples mention below
Example #1
C++ program to demonstrate merge sort technique using which sorting a given input array by implementing merge() function and mergeSort() function and then displaying resulting array as the output on the screen:
#include <iostream>
using namespace std;
//defining the merge function to merge the two sorted halves of the given input array
void merge(int array[], int left, int middle, int right)
{
//dividing the given array into two halves
int fh = middle - left + 1;
int sh = right - middle;
//creating two temporary arrays
int t1[fh], t2[sh];
//copying the data from the two halves into two temporary arrays
for (int m = 0; m < fh; m++)
t1[m] = array[left + m];
for (int n = 0; n < sh; n++)
t2[n] = array[middle + 1 + n];
//merging the temporary arrays into a single array
int a = 0;
int b = 0;
int c = left;
while (a < fh && b < sh) {
if (t1[a] <= t2[b]) {
array[c] = t1[a];
a++;
}
else {
array[c] = t2[b];
b++;
}
c++;
}
while (a < fh) {
array[c] = t1[a];
a++;
c++;
}
while (b < sh) {
array[c] = t2[b];
b++;
c++;
}
}
//sorting each of the divided arrays using mergeSort() function
void mergeSort(int array[],int left,int right){
if(left>=right){
return;
}
int middle =left+ (right-left)/2;
mergeSort(array,left,middle);
mergeSort(array,middle+1,right);
merge(array,left,middle,right);
}
// function to print the resulting array
void printArray(int Array[], int size)
{
for (int d = 0; d < size; d++)
cout << Array[d] << " ";
}
// defining the main function
int main()
{
int array[] = { 20, 50, 10, 5, 25, 45 };
int array_size = sizeof(array) / sizeof(array[0]);
cout << "The elements of the input array before sorting are: \n";
printArray(array, array_size);
mergeSort(array, 0, array_size - 1);
cout << "\nThe elements of the input array after sorting are: \n";
printArray(array, array_size);
return 0;
}The output of the above program is shown in the snapshot below:
In the above program, we have found the middle point, which divides the given input array into two parts. Then we are defining merge() , mergeSort() and printArray() functions. Then we are defining the main function within which we are dividing the given array and then calling mergeSort() function to sort each divided array and then calling merge() function to merge the sorted arrays and then finally calling printArray() function to display the resulting array as the output on the screen.
Example #2
C++ program to demonstrate merge sort technique using which sorting a given input array by implementing merge() function and mergeSort() function and then displaying resulting array as the output on the screen:
#include <iostream>
using namespace std;
//defining the merge function to merge the two sorted halves of the given input array
void merge(int array[], int left, int middle, int right)
{
//dividing the given array into two halves
int fh = middle - left + 1;
int sh = right - middle;
//creating two temporary arrays
int t1[fh], t2[sh];
//copying the data from the two halves into two temporary arrays
for (int m = 0; m < fh; m++)
t1[m] = array[left + m];
for (int n = 0; n < sh; n++)
t2[n] = array[middle + 1 + n];
//merging the temporary arrays into a single array
int a = 0;
int b = 0;
int c = left;
while (a < fh && b < sh) {
if (t1[a] <= t2[b]) {
array[c] = t1[a];
a++;
}
else {
array[c] = t2[b];
b++;
}
c++;
}
while (a < fh) {
array[c] = t1[a];
a++;
c++;
}
while (b < sh) {
array[c] = t2[b];
b++;
c++;
}
}
//sorting each of the divided arrays using mergeSort() function
void mergeSort(int array[],int left,int right){
if(left>=right){
return;
}
int middle =left+ (right-left)/2;
mergeSort(array,left,middle);
mergeSort(array,middle+1,right);
merge(array,left,middle,right);
}
// function to print the resulting array
void printArray(int Array[], int size)
{
for (int d = 0; d < size; d++)
cout << Array[d] << " ";
}
// defining the main function
int main()
{
int array[] = { 100, 50, 20, 80, 10, 40 };
int array_size = sizeof(array) / sizeof(array[0]);
cout << "The elements of the input array before sorting are: \n";
printArray(array, array_size);
mergeSort(array, 0, array_size - 1);
cout << "\nThe elements of the input array after sorting are: \n";
printArray(array, array_size);
return 0;
}The output of the above program is shown in the snapshot below:
In the above program, we have found the middle point, which divides the given input array into two parts. Then we are defining merge() , mergeSort() and printArray() functions. Then we are defining the main function within which we are dividing the given array and then calling mergeSort() function to sort each divided array and then calling merge() function to merge the sorted arrays and then finally calling printArray() function to display the resulting array as the output on the screen.
Recommended Articles
This is a guide to Merge sort C++. Here we discuss the concept of merge sort in C++ with corresponding programming examples and their outputs to demonstrate them. You may also have a look at the following articles to learn more –
