// 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 two equal sized sorted lists of\n"
    << "numbers in increasing order\n"
    <<"\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,j;
  int tempIdx;
  tempIdx=0;                    // index into temp array
  lowerLeft=0;                  // first index of left half
  lowerRight=lowerLeft+n/2;     // last index of left half
  upperLeft=lowerRight+1;       // first index of right half
  upperRight=n-1;               // last index of right half

  // Merge the arrays; loop until one half is exhausted
  for(i=lowerLeft,j=lowerRight;i<=upperLeft&&j<=upperRight;tempIdx++) {
    if(array[i]<=array[j])
      temp[tempIdx]=array[i++];
    else
      temp[tempIdx]=array[j++];
  }
  // copy over remaining element fron unexhausted half
  for(;i<=upperLeft;tempIdx++)
    temp[tempIdx]=array[i++];
  for(;j<=upperRight;tempIdx++)
    temp[tempIdx]=array[j++];
  // Copy back
  for (tempIdx=0;tempIdx<n;tempIdx++)
    array[tempIdx]=temp[tempIdx];
}

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;
}