Merge Sort In C++ With Examples

C++ Merge Sort Technique.

Merge sort algorithm uses the “divide and conquer” strategy wherein we divide the problem into subproblems and solve those subproblems individually.

These subproblems are then combined or merged together to form a unified solution.

=> Read Through The Popular C++ Training Series Here.

Overview

Merge sort is performed using the following steps:

#1) The list to be sorted is divided into two arrays of equal length by dividing the list on the middle element. If the number of elements in the list is either 0 or 1, then the list is considered sorted.

#2) Each sublist is sorted individually by using merge sort recursively.

#3) The sorted sublists are then combined or merged together to form a complete sorted list.

General Algorithm

The general pseudo-code for the merge sort technique is given below.

Declare an array Arr of length N
If N=1, Arr is already sorted
If N>1,
Left = 0, right = N-1
Find middle = (left + right)/2
Call merge_sort(Arr,left,middle) =>sort first half recursively
Call merge_sort(Arr,middle+1,right) => sort second half recursively
Call merge(Arr, left, middle, right) to merge sorted arrays in above steps.
Exit

As shown in the above pseudo code, in merge sort algorithm we divide the array into half and sort each half using merge sort recursively. Once sub-arrays are sorted individually, the two sub-arrays are merged together to form a complete sorted array.

Pseudo Code For Merge Sort

Following is the pseudo code for merge sort technique. First, we have a procedure merge sort to split the array into halves recursively. Then we have a merge routine that will merge the sorted smaller arrays to get a complete sorted array.

procedure mergesort( array,N )
array – list of elements to be sorted
N – number of elements in the list
begin
if ( N == 1 ) return array
var array1 as array = a[0] ... a[N/2]
var array2 as array = a[N/2+1] ... a[N]
array1 = mergesort(array1)
array2 = mergesort(array2)
return merge( array1, array2 )
end procedure
procedure merge(array1, array2 )
	array1 – first array
	array2 – second array
begin
var c as array
while ( a and b have elements )
if ( array1[0] > array2[0] )
        	 add array2 [0] to the end of c
         	remove array2 [0] from array2
else
         	add array1 [0] to the end of c
        	 remove array1 [0] from array1
end if
end while
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
end while
   
while ( b has elements )
add b[0] to the end of c
remove b[0] from b
end while
   
return c
end procedure

Let us now illustrate the merge sort technique with an example.

Illustration

The above illustration can be shown in a tabular form below:

As shown in the above representation, first the array is divided into two sub-arrays of length 4. Each sub-array is further divided into two more sub arrays of length 2. Each sub-array is then further divided into a sub-array of one element each. This entire process is the “Divide” process.

Once we have divided the array into sub-arrays of single element each, we now have to merge these arrays in sorted order.

As shown in the illustration above, we consider each subarray of a single element and first combine the elements to form sub-arrays of two elements in sorted order. Next, the sorted subarrays of length two are sorted and combined to form two sub-arrays of length four each. Then we combine these two sub-arrays to form a complete sorted array.

Iterative Merge Sort

The algorithm or technique of merge sort we have seen above uses recursion. It is also known as “recursive merge sort”.

We know that recursive functions use function call stack to store the intermediate state of calling function. It also stores other bookkeeping information for parameters etc. and poses overhead in terms of storing activation record of calling the function as well as resuming the execution.

All these overheads can be gotten rid of if we use iterative functions instead of recursive ones. The above merge sort algorithm also can be converted easily into iterative steps using loops and decision-making.

Like recursive merge sort, iterative merge sort also has O (nlogn) complexity hence performance wise, they perform at par with one another. We simply are able to lower the overheads.

In this tutorial, we have been concentrating on recursive merge sort and next, we will implement recursive merge sort using C++ and Java languages.

Given below is an implementation of merge sort technique using C++.

#include <iostream>
using namespace std;
void merge(int *,int, int , int );
void merge_sort(int *arr, int low, int high)
{
    int mid;
    if (low < high){
        //divide the array at mid and sort independently using merge sort
        mid=(low+high)/2;
        merge_sort(arr,low,mid);
        merge_sort(arr,mid+1,high);
        //merge or conquer sorted arrays
        merge(arr,low,high,mid);
    }
}
// Merge sort 
void merge(int *arr, int low, int high, int mid)
{
    int i, j, k, c[50];
    i = low;
    k = low;
    j = mid + 1;
    while (i <= mid && j <= high) {
        if (arr[i] < arr[j]) {
            c[k] = arr[i];
            k++;
            i++;
        }
        else  {
            c[k] = arr[j];
            k++;
            j++;
        }
    }
    while (i <= mid) {
        c[k] = arr[i];
        k++;
        i++;
    }
    while (j <= high) {
        c[k] = arr[j];
        k++;
        j++;
    }
    for (i = low; i < k; i++)  {
        arr[i] = c[i];
    }
}
// read input array and call mergesort
int main()
{
    int myarray[30], num;
    cout<<"Enter number of elements to be sorted:";
    cin>>num;
    cout<<"Enter "<<num<<" elements to be sorted:";
    for (int i = 0; i < num; i++) { cin>>myarray[i];
    }
    merge_sort(myarray, 0, num-1);
    cout<<"Sorted array\n";
    for (int i = 0; i < num; i++)
    {
        cout<<myarray[i]<<"\t";
    }
}

Output:

Enter the number of elements to be sorted:10

Enter 10 elements to be sorted:101 10 2 43 12 54 34 64 89 76

Sorted array

2       10      12      34      43      54      64      76      89      101

In this program, we have defined two functions, merge_sort and merge. In the merge_sort function, we divide the array into two equal arrays and call merge function on each of these sub arrays. In merge function, we do the actual sorting on these sub arrays and then merge them into one complete sorted array.

Next, we implement the Merge Sort technique in Java language.

class MergeSort  {  
void merge(int arr[], int beg, int mid, int end)  {  
 	int left = mid - beg + 1;  
	int right = end - mid;  
  
	int Left_arr[] = new int [left];  
	int Right_arr[] = new int [right];  
  
	for (int i=0; i<left; ++i)  
	Left_arr[i] = arr[beg + i];  
  
	for (int j=0; j<right; ++j)  
	Right_arr[j] = arr[mid + 1+ j];  
    
	int i = 0, j = 0;  
	int k = beg;  
	while (i<left&&j<right){  
		if (Left_arr[i] <= Right_arr[j])  {  
			arr[k] = Left_arr[i];  
			i++;  
		}	  
		else{	  
			arr[k] = Right_arr[j];  
			j++;  
		}  
		k++;  
	}  
	while (i<left)  {  
		arr[k] = Left_arr[i];  
		i++; k++;  
	}  
  	while (j<right){  
		arr[k] = Right_arr[j];  
		j++;k++;  
	}  
}  
  
void merge_sort(int arr[], int beg, int end)  {  
	if (beg<end)  {  
		int mid = (beg+end)/2;  
		merge_sort(arr, beg, mid);  
		merge_sort(arr , mid+1, end);  
		merge(arr, beg, mid, end);  
	}  
}  
}
class Main{
	public static void main(String args[])  
	{  
		int arr[] = {101,10,2,43,12,54,34,64,89,76}; 
		System.out.println("\nInput Array");  
		for(int i =0; i<arr.length;i++)  
		{  
   			 System.out.print(arr[i]+" ");  
		}  
		MergeSort ob = new MergeSort();  
		ob.merge_sort(arr, 0, arr.length-1);  
  
		System.out.println("\nArray sorted using merge sort");  
		for(int i =0; i<arr.length;i++)  
		{  
    		System.out.print(arr[i]+" ");  
		}  
	}  
}  

Output:

Input Array

101    10    2    43    12    54    34     64    89   76

Array sorted using merge sort

2    10    12    34    43   54   64    76    89   101

In Java implementation as well, we use the same logic as we used in C++ implementation.

Merge sort is an efficient way of sorting lists and mostly is used for sorting linked lists. As it uses a divide and conquer approach, merge sort technique performs equally efficient for smaller as well as larger arrays.

Complexity Analysis Of The Merge Sort Algorithm

We know that in order to perform sorting using merge sort, we first divide the array into two equal halves. This is represented by “log n” which is a logarithmic function and the number of steps taken is log (n+1) at the most.

Next to find the middle element of the array we require single step i.e. O(1).

Then to merge the sub-arrays into an array of n elements, we will take O (n) amount of running time.

Thus the total time to perform merge sort will be n (log n+1), which gives us the time complexity of O (n*logn).

The time complexity for merge sort is the same in all three cases (worst, best and average) as it always divides the array into sub-arrays and then merges the sub-arrays taking linear time.

Merge sort always takes an equal amount of space as unsorted arrays. Hence when the list to be sorted is an array, merge sort should not be used for very large arrays. However, merge sort can be used more effectively for linked lists sorting.

Conclusion

Merge sort uses the “divide and conquer” strategy which divides the array or list into numerous sub arrays and sorts them individually and then merges into a complete sorted array.

Merge sort performs faster than other sorting methods and also works efficiently for smaller and larger arrays likewise.

We will explore more about Quick Sort in our upcoming tutorial!

=> Watch Out The Beginners C++ Training Guide Here.