#include   <stdio.h>
#include   <dos.h>
#include   <conio.h>
#include   <time.h>
#include   <stdlib.h>

  void get_s(int s[],int n);
  void display_s(int s[],int n);
  void mergesort(int low, int high, int s[]);
  void merge(int low,int mid , int high, int s[]);
  int main(void)
   {
	struct  time start,end;
	int low,high;
	clrscr();
	int n,s[100];
	printf("Enter n:");
	scanf("%d",&n);
	get_s(s,n);
	low = 0;
	high = n-1 ;
	gettime(&start);
	mergesort(low,high,s);
	gettime(&end);
	display_s(s,n);
 int ss,ms ;
    if(end.ti_sec>start.ti_sec) ss =end.ti_sec-start.ti_sec ;
    else ss = start.ti_sec-end.ti_sec    ;
    if(end.ti_hund>start.ti_hund) ms= end.ti_hund-start.ti_hund ;
    else ms =start.ti_hund-end.ti_hund  ;

    printf("\n\n\nThe Differ Time %d:%d",
	ss,ms);

   getch();
   return 0;
  }
  void get_s(int s[],int n)
  {
      randomize();
   for(int i = 0; i < n; i ++)
     s[i] = rand() % 100 ;

   printf("\n\nBefor Sort:\n\n");
   for(i = 0; i < n; i++) {
	if (i % 10 == 0) printf("\n") ;
       printf("%5d", s[i]);
      }

  }
void display_s(int s[],int n)
  {
    printf("\n\nAfter Sort:\n\n");
   for(int i = 0; i < n; i++) {
       if (i % 10 == 0) printf("\n") ;
       printf("%5d", s[i]); }

  }
void mergesort (int low , int high, int s[])
  {
	int mid ;
	if (low < high ){ delay(50);
	  mid = (low + high)/2;
	  mergesort(low,mid,s);
	  mergesort(mid + 1 ,high,s);
	  merge(low,mid,high,s);
	  }
  }
void merge(int low , int mid , int high, int s[])
  {
	int h,i,j,k;
	int b[100];
	h = low;
	i = low ;
	j = mid + 1 ;
	while (h <= mid && j <= high){
	  if (s[h] <= s[j]){
	    b[i] = s[h];
	    h++;
	    }
	    else {
	      b[i] = s[j] ;
	      j++;
	      }
	  i++;
	}
	if (h > mid)
	  for(k = j ; k <= high; k++){
	    b[i] = s[k];
	    i++;
	  }
	    else
	      for (k = h ; k <= mid ; k++){
		b[i] = s[k] ;
		i++;
	      }
	for (k = low ; k <= high ; k++)
	s[k] = b[k];
  }