/* THIS PROGRAM SORTS 'N' ELEMENTS BY USING MERGE-SORT TECHNIQUE*/

/* HERE THE FUNCTION "sizeArray()" RETURN NUMBER OF ELEMENTS*/

/* THE FUNCTION "mSort()" DIVIDES THE ELEMENTS INTO TWO SUB-LISTS  */

/* SAME PROCEDURE APPLIED TO THOSE SUB-LISTS UNTIL SIZE OF THE SUB-LIST

 IS EQUAL TO ONE. */

/* THE PROCEDURE "merge()" MERGES TWO SORTED SUB-LISTS INTO A SINGLE SORTED LIST*/

#include"Array.cpp"

class MergeSort : public Array

{

public:

int sizeArray();

void mSort(int , int);

void merge(int, int, int);

};

int MergeSort :: sizeArray()

{

 return n;

}

/* THE ROUTINE "mSort()" TAKES TWO ARGUMETS*/

/* ONE IS INDEX OF BEGINING ELEMENT AND ANOTHER ONE IS END OF THE LIST*/

void MergeSort :: mSort(int p, int q)

{

  int mid;

  if(p<q)

  {

   mid=(p+q)/2;

   mSort(p, mid);

   mSort(mid+1,q);

   merge(p, mid, q);

  }

}

/* THE ROUTINE "merge()" TAKES THREE ARGUMENTS*/

/* FIRST ONE IS INDEX OF BEGINING ELEMENT AND LAST ONE IS END OF SECOND LIST*/

/* MIDDLE ONE IS END OF FIRST LIST */

/* HERE WE CAREFULLY USE TEMPORARY ARRAY "temp" */

void MergeSort:: merge(int p, int mid, int q)

{

   int i,j,k, *temp;

   temp=new int[q-p+1];

   i=p; j=mid+1; k=0;

   while((i<=mid)&&(j<=q))

   {

    if(a[i]<a[j]) { temp[k]=a[i]; i++; k++; }

    else{ temp[k]=a[j]; j++; k++; }

   }

   if(i>mid){

        do{ temp[k]=a[j]; j++; k++; }while(j<=q);

   }

   else{

        do{ temp[k]=a[i]; i++; k++; }while(i<=mid);

   }

   k=0;

   for(i=p;i<=q;i++)

   {

    a[i]=temp[k]; k++;

   }

}

void main()

{

 int size;

 MergeSort ms;

 ms.readArray();

 size=ms.sizeArray();

 ms.mSort(0, size-1);

 ms.printArray();

}