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.

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

**Also Read:**

**C Program to Make Simple Calculator****Armstrong Number Program in C****Fibonacci Series Program in C****Decimal to Binary Conversion Program in C****Reverse a String in C****Program to Reverse a Number in C****Hello World Program in C****Palindrome Program in C****Leap Year Program in C****Factorial Program in C****Prime Number Program in C****Program to print prime numbers from 1 to n****Anagram program in C.****Calculate LCM Program in C.****Addition of Two Numbers in C****Matrix Multiplication Program in C.****Playfair Cipher Program in C.****GCD Program in C.****Tower of Hanoi in C.****First Fit Program in C****Swapping of two numbers in C****Menu Driven Program in C.****Odd or Even number program in C****Round Robin Program in C****Simple Interest Program in C****Quadratic Equation Program in C.****Bubble Sort Program in C.****Insertion Sort Program in C.****Quick Sort Program in C.**