归并排序详解

 归并排序采用的是分治的思想，先将待排序的部分分为左部分和右部分，左右两部分在不断细分，再将左边和右边分别合并排序，最后将左边和右边合并排序；

#include
using namespace std;
const int N=1e5+10;
int a[N],temp[N],n;//temp数组用来中间过渡存储

void merge(int l,int r){//归并函数 
    if(l>=r) return;
    int mid=l+r>>1;
    merge(l,mid);//归并左区间 
    merge(mid+1,r);//归并右区间 
    int k=0;
    int i=l,j=mid+1;//一起归并 
    while(i<=mid&&j<=r){
        if(a[i]>n;
    for(int i=0;i>a[i];
    merge(0,n-1);
    for(int i=0;i 
 输入样例：
 
5
3 1 2 4 5
 
输出样例：
 
1 2 3 4 5
 
对于样例：3，1，2，4，5：
 
先将其分为3，1，2和4，5两部分，再将3，1，2分为3，1和2两部分，3，1又分为3和1两部分；
 
将4，5分为4和5两部分，再将4和5合并排序为4，5，将3，1合并排序为1，3，再将1，3和2合并排序为1，2，3，再将1，2，3和4，5合并排序为1，2，3，4，5；