如何编写一个二路归并排序的示例代码？

本文共计1077个文字，预计阅读时间需要5分钟。

二路归并排序+基本思想+二路归并排序就是将两个有序子表归并成一个新的有序表。首先，我们有一个用于归并的算法：将两个有序表分别放置在同一个数组中，arr[left]到arr[center-1]为第一个有序表，arr[center]到arr[right]为第二个有序表。

二路归并排序

基本思想

二路归并排序就是将两个有序子表归并成一个有序表。首先我们得有一个算法用于归并：两个有序表放在同一数组的相邻位置上，arr[left]到arr[center-1]为第一个有序表，arr[center]到arr[right]是第二个有序表。每次从两端中取出一个进行比较，小的先放在一个temp数组，最后将比较剩下的直接放到temp中去，最后将temp又复制回arr。这是“治”。
所谓“分”，就是递归地将前半部分和后半部分的数据各自归并排序即可。

算法分析

每一趟归并的时间复杂度为O(n)，共需要进行⌈log2n⌉趟。对应的算法的时间复杂度为O(nlog2n)。归并排序的空间复杂度O(n)。另外，归并排序中归并的算法并不会将相同关键字的元素改变相对次序，所以归并排序是稳定的。
二路归并排序的前提是两个序列本身有序。