- Write a program to illustrate the operation of merge sort on the array A = {3, 41, 52, 26, 38, 57, 9, 49, 08, 15, 72}. The output must show step by step evaluation of the algorithm.
AIM: To write a program to illustrate the operation of merge sort on the array.
Algorithm:
Step1: mergeArray (int a[], int low, int mid, int high)
Step2: if (a<b) return a;
Step3: return b;
Step4: end of if
Step5: set size1= mid-low+1
Step6: set size2= high-mid
Step7: mergeSort (int a[], int size)
Step8: mergeArray(a,l,middleIndex,r);
Step9: mergeSort(a,11);
Step10: END mergeSort
Code:
#include<stdio.h>
int min(int a, int b){
if (a<b) return a;
return b;}
void mergeArray (int a[], int low, int mid, int high)
{
int size1= mid-low+1;
int size2= high-mid;
int leftArr[size1], rightArr[size2];
for (int i=0; i<size1; i)
{
leftArr[i]=a[low+i];
}
for (int i=0; i<size2; i)
{
rightArr[i]=a[mid+1+i];
}
int i=0, j=0, k=low;
while(i<size1 && j<size2)
{
if(leftArr[i]<rightArr[j]) {a[k]=leftArr[i];}
else{a[k]=rightArr[j];}
}
while (i<size1){a[k]=leftArr[i];}
while (j<size2){a[k]=rightArr[j];}
}
void mergeSort (int a[], int size)
{
int step=0;
printf("\n At step %d: - ",step);
for (int i=0; i<size; i)
{
printf("%d ",a[i]);
}
for (int k=1; k<size; k=2)
{
for (int l=0; l<size-1; l+=2k)
{
int middleIndex = min(l+k-1,size-1);
int r = min(l+2*k-1,size-1);
mergeArray(a,l,middleIndex,r);
}
printf("\n At step %d: - ",step);
for(int i=0; i<size; i)
{
printf ("%d ", a[i]);
}
}
}
int main()
{
int a[11]={3,41,52,26,38,57,9,49,8,15,72};
mergeSort(a,11);
return 0;
}
Output:
