Understand mergesort with transition
Code:
#include<stdio.h>
#define max 10
void mergesort(int array[max],int low,int high);
void merge(int array[max],int k,int low,int high);
void main()
{
int array[max],low=0,high=max-1,i;
printf("ENTER VALUE OF ARRAY TO BE SORTED\n");
for(i=low;i<=high;i++)
{
scanf("%d",&array[i]);
}
printf("\nUNDERSTAND MERGE SORT TRANSITIONS\n");
mergesort(array,low,high);
printf("\nSORTED ARRAY IS\n");
for(i=low;i<=high;i++)
{
printf("%d\t",array[i]);
}
}
void mergesort(int array[max],int low,int high)
{
int k;
if(low<high)
{
k=(low+high)/2;
mergesort(array,low,k);
mergesort(array,k+1,high);
merge(array,k,low,high);
}
}
void merge(int array[max],int k,int low,int high)
{
static int f=1;
printf("level %d",f++);
printf(" low=%2d splitter=%2d high=%2d ",low,k,high);
int i,j=k+1,start,end;
start=low;
end=high;
int subarray_size=high-low+1;
int subarray[subarray_size];
for(i=0;i<subarray_size;i++)
{
if(low<=k)
{
if(array[low]<=array[j])
{
subarray[i]=array[low];
low=low+1;
continue;
}
}
if(low>k)
{
--low;
while(i<subarray_size)
{
subarray[i++]=array[j++];
}
break;
}
if(j<=high)
{
if(array[j]<array[low])
{
subarray[i]=array[j];
j=j+1;
continue;
}
}
if(j>high)
{
--j;
while(i<subarray_size)
{
subarray[i++]=array[low++];
}
break;
}
}
i=0;
printf("\n");
while(start<=end)
{
printf("\t%d",subarray[i]);
array[start]=subarray[i];
++i;
++start;
}
printf("\n");
}
