归并排序（模板）（yxcnb）

#include <iostream>

using namespace std;

const int N =1e5+10;

int k[N],t[N];

int n;

void m_sort(int k[],int a,int b)

{

     if(a>=b) return;

     int mid=a+b>>1;

     m_sort(k,a,mid),m_sort(k,mid+1,b);       //递归

     int q=a,p=mid+1,c=0;                           //开始归并

     while(q<=mid && p<=b)

     {

     if(k[q]<=k[p]) t[c++]=k[q++];

     else t[c++]=k[p++];

     }

     while(q<=mid) t[c++]=k[q++];

     while(p<=b) t[c++]=k[p++];

     for(int i=a,j=0;i<=b;i++,j++) k[i]=t[j];   //归并后传回原数组

    }

int main()

{

     scanf("%d",&n);

     for(int i=0;i<n;i++) scanf("%d",&k[i]);

     m_sort(k,0,n-1);

     for(int i=0;i<n;i++) printf("%d ",k[i]);

     return 0;

}