#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<iostream.h>
#include<iomanip.h>
const n=100;
int s[n],q[n];
int co1=0,co2=0;
void mergesort(int low , int high);
void merge(int low , int mid , int high, int &co1);
void quicksort(int low , int high);
void partition(int low , int high , int &pivotpoint, int &co2);
void main()
{
   int i,j,low=0,high=n-1;
   FILE *fpin,*fpout;
   randomize();
   clrscr();
   if((fpin = fopen ("in.txt" , "w")) !=NULL)
      for(i=0;i<n;i++)
      {
	 q[i]=s[i]=rand() % n;
	 fprintf(fpin, "%d ", s[i]);
      }
   else
   {
      cout<<"Can Not Open The Input File.";
      return;
   }
   fclose(fpin);
   cout<<"\t\t";
   textcolor(2);
   cprintf("Random Numbers Are");
   textcolor(7);
   int co=0;
   cout<<"\n\n";
   cout<<" -------------------------------------------------\n";
   for(i=0;i<n;i++)
   {
      co++;
      cout<<"|"<<setw(4)<<s[i];
      if (co%10==0)
      {
	 cout<<"|\n|";
	 cout<<"----|----|----|----|----|----|----|----|----|----|";
	 cout<<"\n";
      }
   }
   cout<<"\n\n";
   textcolor(2);
   cprintf("\n\nPress Any Key!");
   textcolor(7);
   getch();
   mergesort(low,high);
   cout<<"\n\n\n\n\tSorted Numbers By Merge Sort Are\n";
   if ((fpout = fopen ("out.txt" , "w")) != NULL)
   {
      co=0;
      cout<<"\n\n";
      cout<<" -------------------------------------------------\n";
      for(i=0;i<n;i++)
      {
	 co++;
	 cout<<"|"<<setw(4)<<s[i];
	 if (co%10==0)
	 {
	    cout<<"|\n|";
	    cout<<"----|----|----|----|----|----|----|----|----|----|";
	    cout<<"\n";
	 }
	 fprintf(fpout, "%d ", s[i]);
      }
   }
   else
   {
      cout<<"\n\n"<<"Can Not Open The Output File.";
      getch();
      return;
   }
   fclose(fpout);
   cout<<"\n\n";
   textcolor(2);
   cprintf("\n\nPress Any Key!");
   textcolor(7);
   getch();
   quicksort(low,high);
   cout<<"\n\n\n\tSorted Numbers By Quick Sort Are\n";
   co=0;
   cout<<"\n\n";
   cout<<" -------------------------------------------------\n";
   for(i=0;i<n;i++)
   {
      co++;
      cout<<"|"<<setw(4)<<s[i];
      if (co%10==0)
      {
	 cout<<"|\n|";
	 cout<<"----|----|----|----|----|----|----|----|----|----|";
	 cout<<"\n";
      }
   }
   cout<<"\n\n";
   textcolor(2);
   cprintf("\n\nPress Any Key!");
   textcolor(7);
   getch();
   cout<<"\n\n\n\nComparision Of MergeSort="<<co1<<"\n\nCmparision \Of QuickSort="<<co2;
   getch();
}
//****************************************************
void mergesort(int low , int high)
{
   int mid;
   if (low<high)
   {
      mid=(low+high)/2;
      mergesort(low,mid);
      mergesort(mid+1,high);
      merge(low,mid,high,co1);
   }
}
//****************************************************
void merge(int low , int mid , int high, int &co1)
{
   int i=low,j=mid+1,k=low,a;
   int u[n];
   while(i<=mid && j<=high)
   {
      if(s[i]<s[j])
      {
	 u[k]=s[i];
	 i++;
      }
      else
      {
	 u[k]=s[j];
	 j++;
      }
      k++;
      co1++;
   }
   if(i>mid)
      for(a=j;a<=high;a++)
      {
	 u[k]=s[a];
	 k++;
      }
   else
      for(a=i;a<=mid;a++)
      {
	 u[k]=s[a];
	 k++;
      }
   for(a=low;a<=high;a++)
      s[a]=u[a];
}
//****************************************************
void quicksort(int low , int high)
{
   int pivotpoint;
   if (low<high)
   {
      partition(low,high,pivotpoint,co2);
      quicksort(low,pivotpoint-1);
      quicksort(pivotpoint+1,high);
   }
}
//****************************************************
void partition(int low , int high , int &pivotpoint, int &co2)
{
   int i,j,temp;
   int pivotitem;
   pivotitem=q[low];
   j=low;
   for(i=low+1;i<=high;i++)
   {
      if(q[i]<pivotitem)
      {
	 j++;
	 temp=q[i];
	 q[i]=q[j];
	 q[j]=temp;
      }
      co2++;
   }
   pivotpoint=j;
   temp=q[low];
   q[low]=q[pivotpoint];
   q[pivotpoint]=temp;
}