Merge Sort Program in C - [Algorithm With Explanation]

Today we will learn Merge sort program in c. So before starting, we will make you know about Merge sort what actually merge sort is.

Table of Contents

What is Merge Sort?

Merging is the process of combining two or more sorted data lists into a third list such that it is also sorted.

For Example: If the two sorted lists are:

List 1: 3 5 10 23 56

List 2: 4 6 9 60

The merged list will be:

List 3: 3 4 5 6 9 10 23 56 60

Merge sort is based on the process of merging. It requires two sorted sub-sets to create a sorted set. In Merge sort, the elements to be sorted are divided into two equal parts. Each part is sorted and then merged. To sort each half, the same process is used.

Thus, each part is successively divided into two parts until we reach a point where the sub-part is sorted. This will happen when size=1. Since a list of size 1 is sorted, two adjacent sub-lists can be merged to create a sorted sub-lists. The merging process continues until only one list of size n is obtained.

Merge Sort Algorithm:

Merge Sort follows the Divide and Conquer strategy

Divide: Divide an n element sequence into 2 subsequences of size n/2.

Conquer: Sort the two sequences recursively.

Combine: Merge the two sorted sequences into a single sequence.

This process can be done recursively as well as non recursively. We shall study the recursive method which is easier to understand. The recursive function for merge sort can be written as follows:

void MergeSort (int a[20], int low, int high)
{
	int mid;
	if(low<high)  //more than one element
	{
		mid=(low + high) / 2; //Divide a into two sublists
		MergeSort (a,low,mid);  //Sort first sub list
		MergeSort (a,mid+1,high); //sort second sub list
		Merge (a,mid,high);  //Merge sorted sub lists
	}
}

Let us consider the example of sorting 20,40,50,15,30,35,10 and 5.Initially they are all in one list. The elements are successively divided into two sublists till we cannot divide any further i.e, we reach a sublist of size 1. The sublists are then merged to create sorted lists until all elements are in a single list.

In the example shown, each sublist has an even number of elements. However, the list may contain an odd number of elements. In such a case, one sublist will have an additional element.

Let us consider an example of sorting 5 elements

a[5]=[67,57,2,102,33]. Here n=5. Initially low=0 and high=4.

mid=(0+4)/2=2. First half=a[0]…a[2], Second half=a[3]…a[4].

Split a[0:4] into two lists a[0:2] and a[3:4] [67,57,2] [102,33].

1st Step: MergeSort(a,0,2)

Split a[0:2] into two lists a[0:1] and a[2:2] i.e [67,57] [2]

Split a[0:1] into two lists a[0:0] and a[1:1] i.e [67] [57] [2]

Merge a[0:0] and a[1:1] into a[0:1] i.e [57,67] [2]

Merge a[0:1] and a[2:2] into a[0:2] i.e [2,57,67]

At this stage, the first half is sorted. The same steps are carried out for the second half.

Step 2: MergeSort(a,3,4)

Split a[3:4] into two lists a[3:3] and a[4:4] i.e [102] [33].

Merge a[3:3] and a[4:4] into a[3:4] i.e [33,102].

Step 3: Merge (a,0,4) i.e Merge a[0:2] and a[3:4] into a[0:4] which is the sorted list [2,3,57,67,102]

Time Complexity of Merge Sort

The total number of iterations in Merge sort is log2n. In each iteration, n elements are merged. Hence the time complexity of Merge Sort is O(n log2 n). This can be derived as follows:( Here 2 is base)

Advantages:

Best and worst-case efficiency is O(nlog2n). Hence it is very efficient.

It is a stable sorting process.

Disadvantages:

Additional memory is required for the merging process. It is not in-place.

1. Merge Sort Program in C

Below is the program of merge sort in c where after executing the compiler will ask the user to enter the number of integers to sort. Then after entering the numbers, the compiler will print the number in the order according to merge sort algorithm.

#include <stdio.h>
// function to sort the subsection a[i .. j] of the array a[]
void merge_sort(int i, int j, int a[], int aux[]) {
    if (j <= i) {
        return;     // the subsection is empty or a single element
    }
    int mid = (i + j) / 2;
    // left sub-array is a[i .. mid]
    // right sub-array is a[mid + 1 .. j]
    merge_sort(i, mid, a, aux);     // sort the left sub-array recursively
    merge_sort(mid + 1, j, a, aux);     // sort the right sub-array recursively
    int pointer_left = i;       // pointer_left points to the beginning of the left sub-array
    int pointer_right = mid + 1;        // pointer_right points to the beginning of the right sub-array
    int k;      // k is the loop counter
    // we loop from i to j to fill each element of the final merged array
    for (k = i; k <= j; k++) {
        if (pointer_left == mid + 1) {      // left pointer has reached the limit
            aux[k] = a[pointer_right];
            pointer_right++;
        } else if (pointer_right == j + 1) {        // right pointer has reached the limit
            aux[k] = a[pointer_left];
            pointer_left++;
        } else if (a[pointer_left] < a[pointer_right]) {        // pointer left points to smaller element
            aux[k] = a[pointer_left];
            pointer_left++;
        } else {        // pointer right points to smaller element
            aux[k] = a[pointer_right];
            pointer_right++;
        }
    }
    for (k = i; k <= j; k++) {      // copy the elements from aux[] to a[]
        a[k] = aux[k];
    }
}
int main() {
  int a[100], aux[100], n, i, d, swap;
  printf("Enter number of elements in the array:\n");
  scanf("%d", &n);
  printf("Enter %d integers\n", n);
  for (i = 0; i < n; i++)
    scanf("%d", &a[i]);
  merge_sort(0, n - 1, a, aux);
  printf("Printing the sorted array:\n");
  for (i = 0; i < n; i++)
     printf("\t%d", a[i]);
  return 0;
}

Output:

2. Merge Sort Program Using Recursion

In this program, we will use recursion. Recursion means the program in which function calls itself.

#include<stdio.h>
int arr[20];       // array to be sorted
int main()
{
  int n,i;
  printf("Enter the size of array\n");  // input the elements
  scanf("%d",&n);
  printf("Enter the elements:");
  for(i=0;i<n;i++)
    scanf("%d",&arr[i]);
  merge_sort(arr,0,n-1);  // sort the array
  printf("Sorted array:");  // print sorted array
  for(i=0;i<n;i++)
    printf("\t%d",arr[i]);
  return 0;
}
int merge_sort(int arr[],int low,int high)
{
  int mid;
  if(low<high)
  {
    mid=(low+high)/2;
   // Divide and Conquer
    merge_sort(arr,low,mid);
    merge_sort(arr,mid+1,high);
   // Combine
    merge(arr,low,mid,high);
  } 
  return 0;
}
int merge(int arr[],int l,int m,int h)
{
  int arr1[10],arr2[10];  // Two temporary arrays to
        //hold the two arrays to be merged
  int n1,n2,i,j,k;
  n1=m-l+1;
  n2=h-m;
  for(i=0;i<n1;i++)
    arr1[i]=arr[l+i];
  for(j=0;j<n2;j++)
    arr2[j]=arr[m+j+1];
  arr1[i]=9999;  // To mark the end of each temporary array
  arr2[j]=9999;
  i=0;j=0;
  for(k=l;k<=h;k++)  //process of combining two sorted arrays
  {
    if(arr1[i]<=arr2[j])
      arr[k]=arr1[i++];
    else
      arr[k]=arr2[j++];
  }
  return 0;
}

Output:

3. Merge Sort without Without Recursion

#include <stdio.h>
#define MAX 30
int main()
{
	int arr[MAX],temp[MAX],i,j,k,n,size,l1,h1,l2,h2;
	printf("Enter the number of elements : ");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		printf("Enter element %d : ",i+1);
		scanf("%d",&arr[i]);
	}
	printf("Unsorted list is : ");
	for( i = 0 ; i<n ; i++)
		printf("%d ", arr[i]);
	/*l1 lower bound of first pair and so on*/
	for(size=1; size < n; size=size*2 )
	{
		l1=0;
		k=0;  /*Index for temp array*/
		while( l1+size < n)
		{
			h1=l1+size-1;
			l2=h1+1;
			h2=l2+size-1;
			/* h2 exceeds the limlt of arr */
			if( h2>=n ) 
				h2=n-1;
			/*Merge the two pairs with lower limits l1 and l2*/
			i=l1;
			j=l2;
			while(i<=h1 && j<=h2 )
			{
				if( arr[i] <= arr[j] )
					temp[k++]=arr[i++];
				else
					temp[k++]=arr[j++];
			}
			while(i<=h1)
				temp[k++]=arr[i++];
			while(j<=h2)
				temp[k++]=arr[j++];
			/**Merging completed**/
			/*Take the next two pairs for merging */
			l1=h2+1; 
		}
		for(i=l1; k<n; i++) 
			temp[k++]=arr[i];
		for(i=0;i<n;i++)
			arr[i]=temp[i];
		printf("\nSize=%d \nElements are : ",size);
		for( i = 0 ; i<n ; i++)
			printf("%d ", arr[i]);
	}/*End of for loop */
	printf("\nSorted list is :\n");
	for( i = 0 ; i<n ; i++)
		printf("%d ", arr[i]);
	printf("\n");
	return 0;
}

Output: