算法分析：

• 时间复杂度$O(nlogn)$
• 思想：归并排序是一种基于分治的思想。
• 实现步骤：给定一个待排序数组q[N],其中L为左端点，R为右端点。
  1.确定分界点：int mid = l + r >> 1;
  2.递归处理左右区间：merge_sort(q, l,mid) , merge_sort(q,mid + 1,r);
  3.调整区间：合二为一

code:

#include<iostream>
using namespace std;const int N = 100010;int n;
int q[N], tmp[N];void merge_sort(int q[], int l, int r)
{if(r == l) return;int mid = l + r >> 1;merge_sort(q, l, mid);merge_sort(q, mid + 1, r);int i = l, j = mid + 1, k = 0;while(i <= mid && j <= r){if(q[i] < q[j]) tmp[k ++] = q[i ++];else tmp[k ++] = q[j ++];}while(i <= mid) tmp[k ++] = q[i ++];while(j <= r) tmp[k ++] = q[j ++];for(int i = l, j = 0; i <= r; i ++, j ++){q[i] = tmp[j];}
}
int main()
{scanf("%d", &n);for(int i = 0; i < n; i ++ ) scanf("%d", &q[i]);merge_sort(q, 0, n - 1);for(int i = 0; i < n; i ++) printf("%d ", q[i]);return 0;
}

总结：

1.需要一个tmp辅助数组。
2.最后将tmp数组转换回来的时候要注意下标。
3.归并常考点：统计逆序对的数量。
4.归并排序是一个稳定排序。

例题：

P1908 逆序对