归并排序解析

#include
#include
#include

using namespace std;
const int N=1000010;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r)
{
    if(l>=r)return ;
    int mid=l+r>>1向下取整,i=l,j=mid+1; int mid = l + r + 1>> 1;//注意mid是向上取整（防止数据过少而造成死递归，即防止mid=1
    merge_sort(q,l,mid),merge_sort(q,j,r);//递归操作
    int k=0;
    while(i<=mid&&j<=r)
    if(q[i]     else tmp[k++]=q[j++];
    while(i<=mid)tmp[k++]=q[i++];//判断是否有剩余部分并放到暂时数组中。
    while(j<=r)tmp[k++]=q[j++];
    
    for (k=0,i = l; i <=r; k++,i ++ )//原数列的某一部分，暂时数组则从0开始，放回是因为递归操作是对原数组进行的
    q[i]=tmp[k];
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    merge_sort(q,0,n-1);
    for (int i = 0; i < n; i ++ )
    printf("%d ",q[i]);
    return 0;
}