C program of Merge Sort Algorithm | C code Champ

C program of Merge Sort Algorithm | C code Champ

2132
4
SHARE

C program of Merge sort algorithm : Merge 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.

 

C program of Merge Sort Algorithm | C code Champ

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+.

 

4 COMMENTS

  1. 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.

  2. 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 .

LEAVE A REPLY