Objective: C program to perform merge sort using the divide and conquer technique.
Concept: Merge sort describes this process using recursion and a function Merge which merges two sorted sets. As another example of Divide and conquer a sorting algorithm that in the worst case its complexity is O(n log n). This algorithm is called Merge Sort.
Algorithm:
Merge sort is a perfect example of a successful application of the divide-and-conquer technique.
1. Split array A[1..n] in two and make copies of each half in arrays B[1.. n/2 ] and C[1.. n/2 ]
2. Sort arrays B and C
3. Merge sorted arrays B and C into array A as follows:
a) Repeat the following until no elements remain in one of the arrays:
i. compare the first elements in the remaining unprocessed portions of the arrays
ii. copy the smaller of the two into A, while increment the index indicating the unprocessed portion of that array
b) Once all elements in one of the arrays are processed, copy the remaining unprocessed elements from the other array into A.
Source code:
#include
#include
int a[50];
void merge(int,int,int);
void merge_sort(int low,int high)
{
int mid;
if(low<high)< span="">
{
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("\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();
}
SAMPLE OUTPUT
