首先介绍归并排序：
国际惯例，我引入比喻，各位看官随意听听抽象代师。
我将归并排序比喻成“斗兽场排序”，什么意思呢？就是将原来的一个数组一分为二，将数字比喻斗士，A组B组斗士。
第一位A组斗士和B组斗士死斗（比大小） 败者食尘，落入败者监狱（result数组） 一个一个递归过去，这样胜者还留在原来的斗兽场里，最后复制一遍，扫尾一下就ok啦。
'''
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N],res[N];
void m_sort(int q[],int l,int r)
{
if(l>=r) return;
int mid = l+r >>1,k = 0,i = l,j = mid +1;
m_sort(q,l,mid),m_sort(q,mid+1,r);
while(i<=mid && j<= r )
{
if(q[i]<q[j]) res[k++] = q[i++];
else res[k++] = q[j++];
}
while(i<= mid) res[k++] = q[i++];
while (j<= r) res[k++] = q[j++];
for(i=l,j=0;i<=r;i++,j++) q[i]=res[j] ;
}
int main()
{
scanf("%d",&n);
for(int i = 0;i<n;i++) scanf("%d",&q[i]);
m_sort(q,0,n-1);
for(int i = 0;i<n;i++) printf("%d ",q[i]);
return 0;
}
'''
标签：sort,归并,int,斗士,mid,排序,序数 From： https://www.cnblogs.com/ChenDOU/p/17014828.html