// File: Mergesort.cpp
// Mergesort example with questionable class declaration.

/*********************************************************

-> This C++ program is to perform Merge sort
     using iterative method.

-> This program works in microsoft vc++ 6.0 environment.

-> The numbers are sorted in increasing order.

**********************************************************/

#include<iostream.h>
class sorting
{
private:
  double *array;
  int n;
  public:
  void input();
  void output();
  void mergesort();
};

void sorting::input()
{
  cout<<"****************************************************\n"
    <<"This program sorts numbers in increasing order"
    <<"\n\t\tusing Merge sort iterative technique\n"
    <<"****************************************************\n";

  cout<<"Enter how many numbers you are going to enter for sorting ::";
  cin>>n;
  array=new double[n];
  cout<<"Now enter your elements ::\n";
  for(int i=0;i<n;i++)
    cin>>array[i];
}

void sorting::mergesort()
{
  double *temp=new double[n];
  int lowerLeft,lowerRight,upperLeft,upperRight,i;
  int size=1,j,k;
  while(size<n)
  {
     lowerLeft=0;
     k=0;
     while(lowerLeft+size<n)
     {
       lowerRight=lowerLeft+size;
       upperLeft=lowerRight-1;
       upperRight=(lowerRight+size-1<n)?lowerRight+size-1:n-1;
       for(i=lowerLeft,j=lowerRight;i<=upperLeft&&j<=upperRight;k++)
         if(array[i]<=array[j])
           temp[k]=array[i++];
         else
           temp[k]=array[j++];
       for(;i<=upperLeft;k++)
         temp[k]=array[i++];
       for(;j<=upperRight;k++)
         temp[k]=array[j++];
         lowerLeft=upperRight+1;
     }
     for(i=lowerLeft;k<n;i++)
       temp[k++]=array[i];
     for(i=0;i<n;i++)
       array[i]=temp[i];
     size*=2;
  }
}

void sorting::output()
{
  cout<<"Now the sorted numbers are ::\n";
  for(int i=0;i<n;i++)
    cout<<array[i]<<'\t';
  cout<<endl;
}

int main()
{
  sorting obj;
  obj.input();
  obj.mergesort();
  obj.output();
  return 0;
}