// File: MergeSortRec.cpp
// Recursive mergesort example

#include<iostream>

using namespace std;

class Mergesort
{
public:
   void input();
   void mergesort(double *,int );
   void merge(double*,int,double*,int,double*,int);
   void output();
};

int n;
double *array;
void Mergesort::input()
{
   cout<<"Enter the no of elements to be sorted ::";
   cin>>n;
   cout<<"Now enter "<<n<<" elements ::";
   array=new double[n];
   for(int i=0;i<n;i++)
      cin>>array[i];
}

// sorting arr, which has n items
void Mergesort::mergesort(double *arr,int n)
{  int i,j;
   if(n>1)
   {  // copy the first half to array lower
      double *lower;
      lower=new double[n/2];
      for(i=0;i<n/2;i++)
         lower[i]=arr[i];

      // copy the second half to array upper
      double *upper;
      upper=new double[n-n/2];
      for(j=0;i<n;i++,j++)
         upper[j]=arr[i];

      // sort them separately
      mergesort(lower,n/2);
      mergesort(upper,n-n/2);

      // merge the two sorted arrays
      merge(lower,n/2,upper,n-n/2,arr,n);
   }
}







// Combine two sorted arrays into a single sorted array
void Mergesort::merge(double *list1,int list1Size,double *list2,int list2Size,
             double *result,int n)
{  int i,j,k;
   i=j=k=0;
   while(i<list1Size && j<list2Size)
   {
      if(list1[i]<=list2[j])
         result[k]=list1[i],i++;  // this is one statement!
      else
         result[k]=list2[j],j++;
      k++;
   }
   if(i==list1Size) // list1 is exhausted; copy over list2
   {
      // copy the remaing part in array 2
      while(j<list2Size)
         result[k]=list2[j],j++,k++;
   }
   else             // list2 is exhausted; copy over list1
   {
      // copy the remaing part in array 1
      while(i<list1Size)
         result[k]=list1[i],i++,k++;
   }
}

void Mergesort::output()
{
   cout<<"The sorted list is ::\n";
   for(int i=0;i<n;i++)
      cout<<array[i]<<'\t';
   cout<<endl;
}

int main()
{
   Mergesort s;
   cout<<"*************************************";
   cout<<"\nThis program is to sort \n"
      <<"the given numbers in increasing order \n"
      <<"using merge sort algorithm (recursion)\n";
   cout<<"*************************************\n";
   s.input();
   s.mergesort(array,n);
   s.output();
}