merge sort implementation 7

Question

Please look at the above code

#include<stdio.h>
#include<stdlib.h>
void mergesort(int *,int ,int);
void merge1(int *,int ,int ,int);
int main()
{
int low=0,high,n,i,a[100];
 printf("Enter the lenght of array\n");
 scanf("%d",&n);
 high =n-1;
 printf("Enter the array that you want to sort\n");
 for(i=low;i<=high;i++)
 {
 scanf("%d",&a[i]);
 }
 mergesort(a,low,high);
 printf("The sorted array is \n");
 for(i=low;i<=high;i++)
 {
 printf("%d-",a[i]);
 }
 printf("MERGE sorted");
 return 0;
}
void mergesort(int a[],int low,int high)
{
 int mid;
 if(low<high)
 {
 mid=(low+high)/2;
 mergesort(a,low,mid);
 mergesort(a,mid+1,high);
 merge1(a,low,mid,high);
 }
}
 void merge1(int a[],int low,int mid,int high)
{
 int i=low,j=mid+1,new_array[100],k=low,m;
 while(i<=mid && j<=high)
 {
 if(a[i]<a[j]) 
 {
 new_array[k]=a[i];
 i++;
 k++;
 }
 else
 {
 new_array[k]=a[j];
 j++;
 k++;
 }
 }
 while(i<=mid)
 {
 new_array[k]=a[i];
 i++;k++;
 }
 while(j<=high) 
 {
 new_array[k]=a[j];
 j++;
 k++;
 }
 for(m=low;m<=high;m++)
 {
 a[m]=new_array[m];
 } 
}

Actually, I implemented merge sort and it is working fine but I want much better code than this . Can anyone make this code much better?

• syb0rg: Do you want the merge sort algorithm to be better, or do you want the sorting to be better?

Answer 1

Coding conventions

1. It is more customary to put one space character before and after a binary operator. So instead of a=1, you should write a = 1.

2. int low=0,high,n,i,a[100]; This is not easy to read, so instead, declare each variable on its own row:

 int low = 0;
 int high;
 .
 .
 .

Implementation

1. new_array[100] This substantially limits your implementation. Of course, in C, you can always overflow it, but it may rewrite relevant data or terminate your program altogether in case your process references a memory location it may not.

2. mid=(low+high)/2; This is a minor nitpick, yet some people suggest writing mid = low + (high - low) / 2. That may avoid overflowing low + high in some (super rare) cases.

General comments

Otherwise, your implementation looks reasonable as you don't write an if hell some novices tend to.

Summa summarum

After mainly correcting the style issues, you may come out with something like this:

#include<stdio.h>
#include<stdlib.h>
void merge(int* a, int low, int mid, int high)
{
 int i = low;
 int j = mid + 1;
 int k = 0;
 int m;
 int* new_array = malloc(sizeof(int) * (high - low + 1));
 while (i <= mid && j <= high)
 {
 if (a[i] < a[j])
 {
 new_array[k++] = a[i++];
 }
 else
 {
 new_array[k++] = a[j++];
 }
 }
 while (i <= mid)
 {
 new_array[k++] = a[i++];
 }
 while (j <= high)
 {
 new_array[k++] = a[j++];
 }
 for (m = low, k = 0; m <= high; m++, k++)
 {
 a[m] = new_array[k];
 }
 free(new_array);
}
void my_mergesort(int a[], int low, int high)
{
 int mid;
 if (low < high)
 {
 mid= low + (high - low) / 2;
 my_mergesort(a, low, mid);
 my_mergesort(a, mid + 1, high);
 merge(a, low, mid, high);
 }
}
int main()
{
 int high;
 int n;
 int i;
 int a[100];
 printf("Enter the lenght of array\n");
 scanf("%d",&n);
 high = n;
 printf("Enter the array that you want to sort\n");
 for(i = 0; i < n; i++)
 {
 scanf("%d", &a[i]);
 }
 my_mergesort(a, 0, n - 1);
 printf("The sorted array is \n");
 for (i = 0; i < n; i++)
 {
 printf("%d ",a[i]);
 }
 puts("\n");
 return 0;
}

Hope that helps.

• SHUBHAM TANDAN: please explain the overflow with low and mid that you have mentioned in your comment i.e mid=(low+high)/2 should be written like mid = low + (high - low) / 2 ?
• coderodde: Assume that an int is a signed 4-byte integer. For the sake of an example, assume that low == 1_000_000_000 and high == 2_000_000_000. The mid should be 1_500_000_000, but it will, in fact, be -1294967296, and the mid ends up being negative.