# Merge Sort in C++

This tutorial is focused on merge sort in C++. If you are interested in learning Merge sort in c++ (A Divide and Conquer algorithm) then see the previous tutorial.

‘Sorting’ in programming refers to the proper arrangement of the elements of an array (in ascending or descending order).

Note: ‘array’ is a collection of variables of the same data type which are accessed by a single name.

‘Merge Sort’ uses the following algorithm to sort the elements of an array:
let the array be -> {1,4,0,8}

1. Split the array into two portions, using the middle element
can be considered as the middle element of the array
2. Treat each portion as a separate array and repeat step 1 on it, do this until two elements remain in a sub-portion
after splitting, the array has two sub-arrays {1,4} and {0,8}
3. arrange the two elements in each sub-array in ascending (or descending) order
1<4, so the left sub-array is {1,4}
0<8, so the right sub-array is {0,8}
4. Merge the sub-arrays in ascending (or descending) order to get back the sorted array
{1,4} and {0,8} when merged together give {0,1,4,8}
Hence, the sorted array is {0,1,4,8}

## Perform Merge Sort in C++

```#include <stdio.h>
#define size 4//pre-defining the array length
void inputArray(int array[],int length)
{
printf("Input %d (integer) elements: ",length);
//note, in the for loop, the intitializing statement is decreasing the value of length by 1 because in arrays, counting starts from 0
for(length--;length>=0;length--){
scanf("%d",&array[length]);
}
}
void printArray(int array[],int length)
{
printf("The elements of the given array are: ");
for(int i=0;i<length;i++)printf("%d ",array[i]);
}
void merge(int array[], int lower, int middle, int upper)
{
int i, j, k;
int left[middle-lower+1];//creating sub-array to store elements in the left portion of 'array[]'
int right[upper-middle];//creating sub-array to store elements in the right portion of 'array[]'
for (i = 0; i < middle-lower+1; i++)//copying appropriate elements from array[] to left[]
left[i] = array[lower + i];
for (j = 0; j < upper-middle; j++)//copying appropriate elements from array[] to right[]
right[j] = array[middle + 1 + j];
i = 0; // initial index of sub-array left[]
j = 0; // initial index of sub-array right[]
k = lower; //initial index of merged array
for (k=lower;i < middle-lower+1 && j < upper-middle;k++)
{//THIS CONDITION SORTS IN ASCENDING ORDER
if (left[i] <= right[j]) array[k] = left[i++];//storing value of left[i] in array[k] if the former is smaller
else array[k] = right[j++];//storing value of right[j] in array[j] if the former is smaller
}
while (i < middle-lower+1) array[k++] = left[i++];//copying back the remaining elements of left[] to array[]
while (j < upper-middle) array[k++] = right[j++];//copying back the remaining elements of right[] to array[]
}
void mergeSort(int array[],int lower,int upper)
{
if(lower>=upper)return;//signifies that array contains only one element
mergeSort(array,lower,(lower+upper)/2);//sorting the left portion of the array
mergeSort(array,((lower+upper)/2)+1,upper);//sorting the right portion of the array
merge(array,lower,(lower+upper)/2,upper);//merging the two portions once sorting is done
}
int main()
{
int array[size];
inputArray(array,size);
mergeSort(array,0,size-1);//passing 'size-1' because array-index-counting starts from 0
printArray(array,size);
return 0;
}```

#### Output:

```Input 4 (integer) elements: 1 4 0 8
The elements of the given array are: 0 1 4 8```

#### Summary of this merge sort program

The execution of the program is explained below:

• inputArray(int[],int) is called to take input integer elements from the user and store them in the array
• mergeSort(int[],int,int) is called to sort the elements of the array with the algorithm explained above
• printArray(int[],int) is called to print the elements of the array (after sorting)

Note:

• the value ‘4’ after size can be changed to any other value in order to get the desired array-length
• since (in C++) arrays are passed by reference, therefore the changes made in mergeSort(int[],int,int) and merge(int[],int,int) stay permanently
• to sort in descending order, just change the sign from ‘<=’ to ‘>‘’in the logical condition inside the 3rd for loop of merge(int[],int,int,int)