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
   4 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 3^rd for loop of merge(int[],int,int,int)