Merge Sort using recursion in C

merge_sort.c

/**
  * Divide  : Divide the n-element array into two n/2-element
  *           sub-arrays
  * Conquer : Sort the two sub-arrays recursively using
  *           merge sort
  * Combine : Merge the two sorted subsequences to form the
  *           sorted array
  **/

#include<stdio.h>

int arr[20];       // array to be sorted

int main()
{
  int n,i;

  printf("Enter the size of array\n");  // input the elements
  scanf("%d",&n);
  printf("Enter the elements:");
  for(i=0; i<n; i++)
    scanf("%d",&arr[i]);

  merge_sort(arr,0,n-1);  // sort the array

  printf("Sorted array:");  // print sorted array
  for(i=0; i<n; i++)
    printf("%d",arr[i]);

  return 0;
}

int merge_sort(int arr[],int low,int high)
{
  int mid;
  if(low<high) {
    mid=(low+high)/2;
    // Divide and Conquer
    merge_sort(arr,low,mid);
    merge_sort(arr,mid+1,high);
    // Combine
    merge(arr,low,mid,high);
  }

  return 0;
}

int merge(int arr[],int l,int m,int h)
{
  int arr1[10],arr2[10];  // Two temporary arrays to
  hold the two arrays to be merged
  int n1,n2,i,j,k;
  n1=m-l+1;
  n2=h-m;

  for(i=0; i<n1; i++)
    arr1[i]=arr[l+i];
  for(j=0; j<n2; j++)
    arr2[j]=arr[m+j+1];

  arr1[i]=9999;  // To mark the end of each temporary array
  arr2[j]=9999;

  i=0;
  j=0;
  for(k=l; k<=h; k++) { //process of combining two sorted arrays
    if(arr1[i]<=arr2[j])
      arr[k]=arr1[i++];
    else
      arr[k]=arr2[j++];
  }

  return 0;
}

thanks

I tried this code in codeblocks and ideone but it seems that time taken for sorting 35 elements is 1.98 seconds and beyond that the code shows terminated due to time out in ideone.

I'm getting a runtime error for thiscode

include<stdio.h>

void merge_sort(int [],int ,int );
void merge(int [], int ,int ,int );

int main()
{
int n,A[n+1],p,r,i;
printf("enter the size of the array\n");
scanf("%d",&n);
printf("enter the elements to be sorted\n");

for(i=0;i<n;i++)
{
    scanf("%d",&A[i]);
}

p=0;

r=n-1;

merge_sort(A,p,r);

printf("the sorted list  is\n");

for(i=0;i<n;i++)
{
    printf("%d\t",A[i]);
}

return 0;

}

void merge_sort(int A[],int p,int r)
{
int q;

if(p<r)
{
    q=(p+r)/2;
    merge_sort(A,p,q);
    merge_sort(A,q+1,r);
    merge(A,p,q,r);
}

}
void merge(int A[],int p, int q , int r)
{
int n1,n2,L[n1],R[n2],i,j,k;
n1=q-p+1;
n2=r-q;

for(i=0;i<n1;i++)
{
    L[i]=A[p+i];
}
L[i]=9999999;

for(j=0;j<n2;j++)
{
    R[j]=A[q+j+1];
}
R[j]=9999999;

i=0;
j=0;

for(k=p;k<=r;k++)
{
    if(L[i]<=R[i])
    {
        A[k]=L[i++];
    }

    else 
    {
        A[k]=R[j++];
    }
}

}

#include<stdio.h>

int arr[20]; // array to be sorted

int merge(int arr[],int l,int m,int h)
{
int arr1[10],arr2[10]; // Two temporary arrays to hold the two arrays to be merged

int n1,n2,i,j,k;
n1=m-l+1;
n2=h-m;

for(i=0; i<n1; i++)
arr1[i]=arr[l+i];
for(j=0; j<n2; j++)
arr2[j]=arr[m+j+1];

arr1[i]=9999; // To mark the end of each temporary array
arr2[j]=9999;

i=0;
j=0;
for(k=l; k<=h; k++) { //process of combining two sorted arrays
if(arr1[i]<=arr2[j])
arr[k]=arr1[i++];
else
arr[k]=arr2[j++];
}
return 0;
}

int merge_sort(int arr[],int low,int high)
{
int mid;
if(low<high) {
mid=(low+high)/2;
// Divide and Conquer
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
// Combine
merge(arr,low,mid,high);
}

return 0;
}

int main()
{
int n,i;

printf("Enter the size of array\n"); // input the elements
scanf("%d",&n);
printf("Enter the elements:");
for(i=0; i<n; i++)
scanf("%d",&arr[i]);

merge_sort(arr,0,n-1); // sort the array

printf("Sorted array:"); // print sorted array
for(i=0; i<n; i++)
printf("%d ",arr[i]);

return 0;
}

`

Hey can someone explain me what's happening at these 2 lines?
merge_sort(arr,low,mid); /This line calling function int merge_sort(int arr[],int low,int high) again? And passing value of high as same as new value of mid?/
merge_sort(arr,mid+1,high);/* Similarly,here this line calling function int merge_sort(int arr[],int low,int high) again? And passing value of low same as mid +1 ? */
What is the right explanation?

can you change this code to descending version?

Helped me a lot. Thanks.

https://gist.github.com/itrare/7602c8dc845ec8dd41fc42b0a5d1680d check this...

1. implement insertion sort,
2. generated 1 M random input
3. write the input in a file

if possible solve this problem