1 /*
 2 归并排序模版
 3 对n个数进行排序
 4 时间复杂度：O(nlogn);
 5 利用分治思想，对比左半边和右边边放入一个暂时的数组进行排序
 6  */
 7 #include <iostream>
 8 using namespace std;
 9 const int maxn = 1005;
10 int a[maxn], t[maxn];
11 void merge(int a[], int l, int m, int r)
12 {
13     int i = l, j = m + 1, x = m, y = r, k = 0;
14     while (i <= x && j <= y)
15         if (a[i] < a[j]) t[k++] = a[i++];
16         else t[k++] = a[j++];
17     while (i <= x) t[k++] = a[i++];
18     while (j <= y) t[k++] = a[j++];
19     for (i = 0; i < k; ++i)
20         a[l + i] = t[i];
21 }
22 void merge_sort(int a[], int l, int r)
23 {
24     if (l >= r) return;
25     int mid = (l + r) / 2;
26     merge_sort(a, l, mid);
27     merge_sort(a, mid + 1, r);
28     merge(a, l, mid, r);
29 }
30 void print()
31 {
32     for (int i = 0; i < 5; ++i)
33         cout << a[i] << " ";
34     cout << endl;
35 }
36 int main()
37 {
38     for (int i = 0; i < 5; ++i)
39         a[i] = 5 - i;
40     print();
41     merge_sort(a, 0, 4);
42     print();
43     return 0;
44 }