归并排序 Acwing 787

归并排序最重要的一部便是归并，我们的模板顺序为：

定义一个中间值，将我们的区间范围一分为二，我们将

这两部分看成两个数组，我们分别将这两个数组进行归并

排序，并且定义一个新的数组，将这两个数组排序好后导入

到这个新数组中，并最后将这个定义的数组输出为原数组，即可

实现归并排序。

 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 }