//归并排序（分治思想）

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

void merge(int data[],int low,int mid,int high)
{
// int temp=(int )malloc(sizeof(int)(high-low+1));
int temp=new int[high-low+1];
//这种恶心人的写法
int p1=low,p2=mid+1,k=0;
while(p1<=mid&&p2<=high){
if(data[p1]>data[p2]) temp[k]=data[p2];
else temp[k]=data[p1];
}
while(p1<=mid) temp[k]=data[p1];
while(p2<=high) temp[k]=data[p2];
for(int i=low,k=0;i<=high;i,k) data[i]=temp[k];
free(temp);
}

void mergesort(int data[],int low,int high){//和快排一样，参数是分治写法
if(low>=high) return;
int mid=(low+high)/2;
mergesort(data,low,mid);
mergesort(data,mid+1,high);
merge(data,low,mid,high);
}

int main(){
int data[]={100,1,3,5,7,9,2,4,6,8,0};
for(int i=1;i<=10;i)
{
cout<<data[i]<<’ ‘;
}
cout<<endl;
mergesort(data,1,10);
for(int i=1;i<=10;i)
cout<<data[i]<<’ ‘;
}

//分析，递归树的角度，每一层都是n，然后logn层 总时间复杂度nlogn
//和快排分析区别我感觉是树每次都是一分为二的，不会出现快排呢种最坏情况
//其次归并的结点是可以为分支结点

//空间复杂度，要开一个一样大小的数组，其次还有递归深度logn，总空间复杂度n

//稳定，data[p1]>=data[p2] temp[k]=data[p1]
//所以归并优势就在于nlogn的稳定排序，缺点在于空间,西大书上说适合外部排序

//那么顺序表和链表都是可以的，归并不就是链表的一个重要应用
//这里和堆一样，最好最坏平均都是一样的，似乎简单选择也是这样