# 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}*

- Split the array into two portions, using the middle element

*4**can be considered as the middle element of the array* - 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}** - 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}** - 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 3^{rd}for loop of merge(int[],int,int,int)

## Leave a Reply