//
//  mergesort.c
//  
//
//  Created by Bibhas Ghoshal on 04/06/22.
//

#include <stdio.h>

int main()
{
    int data[100],i,j,n,temp;
    
    /* Read N */
    
    printf("Give n:");
    scanf("%d",&n);
    printf("\n n = %d \n",n);
    
    for(i=0; i<n; i++)
        scanf("%d",data+i);
    
    printf("\n numbers read are:");
    
    for(i=0; i<n; i++){
        printf("%d",*(data+i));
        printf("\n");
    }
    
   /* Call mergesort */
    
    mergesort(data,0,n-1);
    
  /* print result */
    printf("\n Sorted numbers are:");
    
    for(i=0; i<n; i++){
        printf("\n %d",data[i]);}
        //printf("\n");}
     printf("\n");
}

int mergesort(a,i,j)
int a[],i,j;
{
    int k,mid;
    printf(" Entered with i=%d and j=%d\n",i,j);
    if( i>=j) return 0; // one element in the list
    mid = (i+j)/2;  // splitting point
    mergesort(a,i,mid);
    mergesort(a,mid+1,j);
    merge(a,i,j);
}
    
merge(a,i,j)
int a[],i,j;
{
    int k,b[100],mid,l,start;
/* Intialize */
    
    start = i;
    mid = (i+j)/2;
    k = mid+1;
    l = i;
    
/* form Array b */

    while(i<=mid && k<=j)
      if(a[i] >= a[k])
          b[l++] = a[i++];
       else
           b[l++] = a[k++];
    
    if(i>mid)
        for(;k<=j;) b[l++] = a[k++];
    else
     if(k>j)
        for(;i<=mid;) b[l++] = a[i++];
    
    /* Copy back to array a */
    
    for(l=start;l<=j;l++) a[l] = b[l];
}