**C program of Merge sort algorithm : M**erge sort is based on the **divide-and-conquer** paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with sub problems, we state each sub problem as sorting a sub array *A*[*p* .. *r*]. Initially, *p* = 1 and *r* = *n*, but these values change as we recursive through sub problems.

To sort *A*[*p* .. *r*]:

1. **Divide Step**

If a given array *A* has zero or one element, simply return; it is already sorted. Otherwise, split *A*[*p* .. *r*] into two subarrays *A*[*p* .. *q*] and *A*[*q* + 1 .. *r*], each containing about half of the elements of *A*[*p* .. *r*]. That is, *q* is the halfway point of *A*[*p* .. *r*].

2. **Conquer Step**

Conquer by recursively sorting the two subarrays *A*[*p* .. *q*] and *A*[*q* + 1 .. *r*].

3. **Combine Step**

Combine the elements back in *A*[*p* .. *r*] by merging the two sorted subarrays *A*[*p* .. *q*] and *A*[*q* + 1 .. *r*] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (*A*, *p*, *q*, *r*).

Note that the recursion bottoms out when the subarray has just one element, so that it is trivially sorted.

**Algorithm: Merge Sort**

To sort the entire sequence A[1 .. n], make the initial call to the procedure MERGE-SORT (*A*, 1, *n*).

MERGE-SORT (A, p, r) 1. IF p < r // Check for base case 2. THEN q = FLOOR[(p + r)/2] // Divide step 3. MERGE (A, p, q) // Conquer step. 4. MERGE (A, q + 1, r) // Conquer step. 5. MERGE (A, p, q, r) // Conquer step.

### C program of Merge Sort Algorithm :

#include<stdio.h> #include<conio.h> int a[50]; void merge(int,int,int); void merge_sort(int low,int high) { int mid; if(low<high) { mid=(low+high)/2; merge_sort(low,mid); merge_sort(mid+1,high); merge(low,mid,high); } } void merge(int low,int mid,int high) { int h,i,j,b[50],k; h=low; i=low; j=mid+1; while((h<=mid)&&(j<=high)) { if(a[h]<=a[j]) { b[i]=a[h]; h++; } else { b[i]=a[j]; j++; } i++; } if(h>mid) { for(k=j;k<=high;k++) { b[i]=a[k]; i++; } } else { for(k=h;k<=mid;k++) { b[i]=a[k]; i++; } } for(k=low;k<=high;k++) a[k]=b[k]; } int main() { int num,i; printf("------------------------------------------------------------------\n"); printf("---------------------- Made by C code champ ----------------------\n"); printf("------------------------------------------------------------------\n\n"); printf("\t\t\tMERGE SORT\n"); printf("\nEnter the total numbers: "); scanf("%d",&num); printf("\nEnter %d numbers: \n",num); for(i=1;i<=num;i++) { scanf("%d",&a[i]); } merge_sort(1,num); printf("\nSORTED ORDER: \n"); for(i=1;i<=num;i++) printf("\t%d",a[i]); getch(); }

Let us know if you have any queries regarding above code. If you like our code just like us on Google+.

The info you provide on this website has helped me greatly. Thanks for all of your time & work.

Hi, after reading this remarkable paragraph i am as well cheerful to share my know-how here with colleagues.

Thkans for taking the time to post. It’s lifted the level of debate

Hi, Neat post. There is a problem with your website in internet explorer, would test this IE still is the market chief and a good element of other people will pass over your wonderful writing because of this problem.

Wow, wonderful blog layout! How long have you been blogging for? you made blogging look easy. The overall look of your website is excellent, let alone the content!. Thanks For Your article about C program of Merge Sort Algorithm | C code Champ .

Good to see a taelnt at work. I can’t match that.