Merge sort in C C++
We assume each element of the list/array as a separated list. Each single element is sorted by default so we merge down pair of elements using the merging two sorted arrays method. We continue sorting and merging the sub arrays till we obtain the complete sorted array.
Explanation
We will sort [20 10 30 50 60 90 5 7 2] array using merge sort algorithm.
Assume each element of the array as a different list and then recursively sort each of the list and merge them together.
C program for Merge sort iteratively
#include<stdio.h>
#include<stdlib.h>
void merge(int A[], int l, int mid, int h){
int B[100],i,j,k;
i = l;
j = mid+1;
k = i;
while(i<=mid && j<=h)
{
if(A[i]<A[j])
{
B[k++] = A[i++];
}
else{
B[k++] = A[j++];
}
}
for(;i<=mid;i++)
{
B[k++] = A[i];
}
for(;j<=h;j++)
{
B[k++] = A[j];
}
for(int i=l;i<=h;i++)
{
A[i] = B[i];
}
}
void IMergeSort(int A[], int n)
{
int p,l,h,mid,i;
for(p=2;p<=n;p=p*2)
{
for(i=0;i+p-1<n;i=i+p)
{
l=i;
h=i+p-1;
mid=(l+h)/2;
merge(A,l,mid,h);
}
}
if(p/2<n)
{
merge(A,0,p/2-1,n-1);
}
}
int main()
{
int A[10] = {1,5,2,1,6,3,6,2,5,10};
int i;
IMergeSort(A,10);
for(i=0;i<10;i++)
{
printf("%d ",A[i]);
}
return 0;
}
C program for recursive merge sort
void RMergeSort(int A[], int l, int h)
{
int mid;
if(l<h)
{
mid = (l+h)/2;
RMergeSort(A,l,mid);
RMergeSort(A,mid+1,h);
merge(A,l,mid,h);
}
}
[…] Merge sort in C […]