In this tutorial, you will get program for merge sort in C.
Merge sort runs in O (n log n) running time. It is a very efficient sorting data structure algorithm with near optimal number of comparisons. Recursive algorithm used for merge sort comes under the category of divide and conquer technique. An array of n elements is split around its center producing two smaller arrays. After these two arrays are sorted independently, they can be merged to produce the final sorted array. The process of splitting and merging can be carried recursively till there is only one element in the array. An array with 1 element is always sorted.
An example of merge sort in C is given below. First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.
Program for Merge Sort in C
void mergesort(int a,int i,int j);
void merge(int a,int i1,int j1,int i2,int j2);
printf("Enter no of elements:");
printf("Enter array elements:");
printf("\nSorted array is :");
void mergesort(int a,int i,int j)
mergesort(a,i,mid); //left recursion
mergesort(a,mid+1,j); //right recursion
merge(a,i,mid,mid+1,j); //merging of two sorted sub-arrays
void merge(int a,int i1,int j1,int i2,int j2)
int temp; //array used for merging
i=i1; //beginning of the first list
j=i2; //beginning of the second list
while(i<=j1 && j<=j2) //while elements in both lists
while(i<=j1) //copy remaining elements of the first list
while(j<=j2) //copy remaining elements of the second list
//Transfer elements from temp back to a
If you have any doubts regarding above program for merge sort in C then comment below.