/*******************************************************************************
MergeSort.cpp
归并排序作业
Zhuo Wang.  Email: jimmin2002 { AT } 163.com
*******************************************************************************/

#include <iostream>
#include <fstream>
#include "stdlib.h"
#include <ctime>
 
using namespace std;
 
template<class T>
int Merge(T* data, long* link, long low, long mid, long high, bool ascend)
{
  bool direction=0;
  long i,j,k;
  long* tmplink;
  tmplink=(long *)malloc((high-low+1)*sizeof(long));
  for(i=0;i<high-low+1;i++) tmplink[i]=0;
  i=low;
  j=mid+1;
  k=0;
  while(i<=mid||j<=high)
  {
    direction=0;
    if(i>mid) direction=0;
    else if(j>high) direction=1;
    else {
      if(ascend && data[link[i]]<=data[link[j]]) direction=1;
      if(!ascend && data[link[i]]>data[link[j]]) direction=1;
    }
 
    if(direction)  {
      tmplink[k]=link[i];
      k++;
      i++;
    }
    else {
      tmplink[k]=link[j];
      k++;
      j++;
    }
  }
 
  for(i=low;i<=high;i++)
    link[i]=tmplink[i-low];
  free(tmplink);
}
 
template<class T>
void MergeSort(T* data, long* link, long low, long high, bool ascend)
{
  long mid=0;
  if(low<high)
  {
    mid=(long)((low+high)/2);
    MergeSort(data,link,low,mid,ascend);
    MergeSort(data,link,mid+1,high,ascend);
    Merge(data,link,low,mid,high,ascend);
  }
}
 
int main()
{
  long DATANUM=100000;
  long *data;
  long *link;
  long i;
  cout<<"Please input the total number of random-generated digits(default 100000):";
  cin>>DATANUM;
  if(DATANUM<1) DATANUM=100000;
 
  data=(long *)malloc(DATANUM*sizeof(long));
  link=(long *)malloc(DATANUM*sizeof(long));
  
  /* Create random numbers & initial the index in array "link" */
  srand((unsigned)(time(NULL)));
  for(i=0;i<DATANUM;i++)
  {
    data[i]=(rand()*10000+rand())%(DATANUM*2);
    link[i]=i;
  }
  
  /* Sort! Then show how long of the sorting procedure! */
  clock_t start,end;
  double  duration;
  start=clock();
  MergeSort(&data[0],&link[0],0,DATANUM-1,1);
  end=clock();
  duration = (double)(end-start);
  cout<<"Time elapsed = "<<duration<<" ms!\n";
 
  /* Prlong results to screen! */
  ofstream out;
  char b[255];
  cout<<"Please input a filename to save the results:";
  cin>>b;
  out.open(b,ios::out);
  for(i=0;i<DATANUM;i++) {
    cout<<data[link[i]]<<" ";
    out<<data[link[i]]<<endl;
  }
  out.close();
  system("pause");
  return 0;
}