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?

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.