#include<iostream>
using namespace std;
#include<stdlib.h>
#include<time.h>

int *n;
int size;

void mergeSort(int *,int);//前置處理，讓使用者輸入方便
int Line(int,int,int,int *,int *);//用來切割數列並做遞迴
int compareSort(int,int,int,int,int *,int *);//實際發生「排序」的地方

void main()
{
 n[]={5,7,4,19,2};
 mergesort(n,5);
 for(int i=0;i<size;i++)
 {
  cout<<n[i]<<" ";
 }
    cout<<endl<<endl;
}

void mergesort(int *n,int size)
{
   int Left=0;
   int Right=size-1;
   int *temp=new int[size];
   Line(Left,Right,size,n,temp);
}

int Line(int L,int R,int S,int *n,int *temp)
{
 if(S==1)return L;
 else
 {
  int LSize=(L+S/2-1)-L+1;
  int RSize=R-(L+S/2)+1;
  return compareSort(Line(L,L+S/2-1,LSize,n,temp),Line(L+S/2,R,RSize,n,temp),LSize,RSize,n,temp);
 }
}

int compareSort(int Left,int Right,int LSize,int RSize,int *n,int *temp)
{
 int hold=Left;
 int i=0;
 int L=0;
 int R=0;
 while(true)
 {
  if(n[Left]<=n[Right])
  {
   temp[i]=n[Left];
   i++;
   Left++;
   L++;
  }
  else
  {
   temp[i]=n[Right];
   i++;
   Right++;
   R++;
  }

  int y,x;
  if(L==LSize)
  {
   for(y=0;y<=RSize-R-1;y++)
   {
    temp[i]=n[Right+y];
    i++;
   }
   for(x=0;x<=LSize+RSize-1;x++)n[hold+x]=temp[x];

   return hold;
  }
  else if(R==RSize)
  {
   for(y=0;y<=LSize-L-1;y++)
   {
    temp[i]=n[Left+y];
    i++;
   }
   for(x=0;x<=LSize+RSize-1;x++)n[hold+x]=temp[x];

   return hold;
  }
 } 
}