分治法在每层递归时都有三个步骤：
1.分解原问题为若干个子问题，这些子问题是原问题规模较小的实例；
2.解决子问题，递归求解各子问题，如果子问题规模足够小，则直接求解；
3.合并子问题得到原问题的解。
归并排序完全遵循分治法：
1.分解待排序的n个元素的序列，分成各具有n/2个元素的两个子序列；
2.使用归并排序递归地排序两个子序列；
3.合并两个已排序的子序列得到已排序的答案。
当待排序的子序列只有一个元素时，递归开始“回升”，这种情况下不要做任何工作，因为长度为1的每个序列都已经排好。
#include <bits/stdc++.h> using namespace std; //注意区间状况是[left, mid], (mid, right]; void merge_test(int* a, int left, int mid, int right) { int i, j; int n1 = mid - left + 1; int n2 = right - mid; //建立新数组L[n1 + 1], R[n2 + 1]; int L[n1 + 1], R[n2 + 1]; for (i = 0; i < n1; i++) { L[i] = a[left + i]; } for (i = 0; i < n2; i++) { R[i] = a[mid + i + 1]; } L[n1] = 0x3f3f3f3f, R[n2] = 0x3f3f3f3f;//设为无穷大可不必考虑数组为空的情况 //合并, 从小到大 i = j = 0; for (int k = left; k <= right; k++) { if (L[i] <= R[j]) { a[k] = L[i++]; } else { a[k] = R[j++]; } } } //区间为[left, right]; void merge_sort(int* a, int left, int right) { if (left < right) {//当left = right时区间内只有一个元素,不进行递归; int mid = (left + right)/2; merge_sort(a, left, mid); merge_sort(a, mid + 1, right); merge_test(a, left, mid, right); } } int main() { int n; while (cin >> n) { int a[n]; for (int i = 0; i < n; i++) { cin >> a[i]; } //归并排序，从小到大 merge_sort(a, 0, n - 1);//注意用闭区间 //测试 int flag = 0; for (int i = 0; i < n; i++) { if (flag++) cout << " "; cout << a[i]; } cout << endl; } }
