I have been implementing the merge-sort
algorithm for sorting the data for a long time, each time I use the following source code for implementation.
By secure, I mean, taking care of memory management, loopholes etc.
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
void mergesort(int*,int,int);
void mergeSequence(int*,int,int,int); //Merge the two arrays
void displaySequence(int*);
int n;
int main()
{
int t,test;
int*num=NULL;
int i;
printf("Enter the number of test cases\n", test);
scanf("%d", &test);
assert(test>0);
for(t=0;t<test;t++)
{
printf("Enter the size of the sequence\n", n);
scanf("%d", &n);
assert(n>0);
num=calloc(sizeof(int),n);
assert(num);
printf("Enter the sequence\n");
for(i=0;i<n;i++)
scanf("%d", (num+i));
printf("Sequence before sorting\n");
displaySequence(num);
mergeSort(num,0,(n-1));
printf("Sequence after sorting\n");
display(num);
free(num);
}
return 0;
}
void displaySequence(int*num)
{
int i;
for(i=0;i<n;i++)
printf("%d ", num[i]);
printf("\n");
}
void mergeSort(int*num,int start,int end)
{
int mid;
mid=start+((end-start)/2);
printf("Mid->%d\n", mid);
if(start<end)
{
mergeSort(num,start,mid);
mergeSort(num,(mid+1),end);
mergeSequence(num,start,mid,end);
}
}
void mergeSequence(int*num,int start,int mid,int end)
{
int n1,n2;
int i,j,k;
n1=(mid-start)+1;
n2=(end-mid);
printf("N1->%d\nN2->%d\n", n1,n2);
int left[n1];
int right[n2];
for(i=0;i<n1;i++)
left[i]=num[start+i];
for(i=0;i<n1;i++)
printf("%d ", left[i]);
printf("\n");
for(j=0;j<n2;j++)
right[j]=num[(mid+1)+j];
for(j=0;j<n2;j++)
printf("%d ", right[j]);
printf("\n");
//Now I have two arrays, and I can now merge them
k=start;
i=0;
j=0;
while((k<=end))
{
if(i==n1)
{
num[k]=right[j];
j++;
}
else if(j==n2)
{
num[k]=left[i];
i++;
}
else if(left[i]<=right[j])
{
num[k]=right[j];
j=j+1;
}
else
{
num[k]=left[i];
i=i+1;
}
k++;
}
displaySequence(num);
}