归并排序最重要的一部便是归并，我们的模板顺序为：
定义一个中间值，将我们的区间范围一分为二，我们将
这两部分看成两个数组，我们分别将这两个数组进行归并
排序，并且定义一个新的数组，将这两个数组排序好后导入
到这个新数组中，并最后将这个定义的数组输出为原数组，即可
实现归并排序。
1 #include <iostream> 2 3 using namespace std; 4 5 const int N = 1e5 + 10; 6 7 int n; 8 int a[N],tmp[N]; 9 10 void merge_sort(int a[],int l,int r) 11 { 12 if(l >= r) return ; 13 int mid = l + r >> 1; 14 15 merge_sort(a,l,mid),merge_sort(a,mid + 1 ,r); 16 17 int k = 0,i = l,j = mid + 1; 18 while(i <= mid && j <= r) 19 if(a[i] <= a[j]) tmp[k ++] = a[i ++]; // 等价于tmp[k] = a[i] ;k ++;i ++; 20 else tmp[k ++] = a[j ++]; 21 22 while(i <= mid) tmp[k ++] = a[i ++]; 23 while(j <= r) tmp[k ++] = a[j ++]; 24 25 for (int i = l,j = 0; i <= r; i ++,j ++ ) a[i] = tmp[j]; 26 } 27 28 int main() 29 { 30 scanf("%d", &n); 31 for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); 32 33 merge_sort(a,0,n - 1); 34 35 for (int i = 0; i < n; i ++ ) printf("%d ",a[i]); 36 37 return 0; 38 }