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