本文主要是介绍深入理解归并排序——从归并排序到CDQ分治、归并树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
归并排序
首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
//将有序数组a[]和b[]合并到c[]中
void merge(int a[], int n, int b[], int m, int c[]) {int i, j, k; i = j = k = 0; while (i < n && j < m) { if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } while (i < n) c[k++] = a[i++]; while (j < m) c[k++] = b[j++];
}
可以发现合并有序数列的效率是非常高的，有O(N)此时N = len(a)+len(b)。
这里是我的个人网站：
https://endlesslethe.com/mergesort-and-mergetree-tutorial.html
有更多总结分享，排版也可能会更好看一点=v=
加上一点分治的想法：
从而对于一个数组，我们可以如下的方式二分分治：
如上图所示，最下面是我们需要排序的数组。我们把它分成N个长度为1的区间。那么相邻两个区间进行一次合并的时间为\(O(N)\)。而得到有序的、长度为2的区间后，我们根据它们有序的特点继续合并，那么又在\(O(N)\)的时间内得到了有序的、长度为4的区间。
显然当我们得到最后的排序结果时，一共用了\(O(NlogN)\)的时间，\(O(NlogN)\)的空间。
写成伪代码的形式：
这篇关于深入理解归并排序——从归并排序到CDQ分治、归并树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
