关于归并排序，百度百科是这样定义的：
归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
通过这句话我们可以了解，归排是通过分治实现的。
举个例子：给定了一个数列 \(a\) ，让我们排序：
龟牌的话，就要先一直二分，直到分到最小的板块：
然后就到达了合并的环节，实现方式就是利用另一个数组去表示两个小版块合并成的大板块，用三个指针，\(p,p1,p2\) 分别指向大板块，左边的小板块和右边的小板块的第一个元素，判断左右两个小板块的大小，将较小的元素放入大板块，然后将较小元素的板块和大板块的指针右移，依次类推即可实现。
以上面的排列为例：
因为 4 比 5 要小，所以将 4 先存入大板块的 \(p\) 位置，然后 4 的板块没元素了，于是将 5 放入。
多个元素的话也是同样的道理，用指针一个一个枚举即可：
步骤 1：
步骤 2：
步骤 3：
步骤 4：
最后一直合并到完整的排列就结束了，这就是归并排序的分治思想和模拟实现。
代码实现：
int n, ans;
int a[20], b[20];
void sort(int now[], int temp[], int s, int e) {
if (s == e) return;
int mid = (s + e) >> 1;
sort(now, temp, s, mid), sort(now, temp, mid + 1, e);
int x = s, y = mid + 1, z = s;
while (x <= mid && y <= e)
if (now[x] <= now[y]) temp[z++] = now[x++];
else temp[z++] = now[y++];
while (x <= mid)
temp[z++] = now[x++];
while (y <= e)
temp[z++] = now[y++];
for (x = s; x <= e; x++)
now[x] = temp[x];
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a, b, 1, n);
for (int i = 1; i <= n; i++)
cout << a[i] << ' ';
return 0;
}
归并排序还可以用于求逆序对的问题，可以根据龟牌的思想来想一下这道题怎么做
链接