每日信息：归并排序的时间复杂度是什么？归并排序和快速排序的区别有哪些？

归并排序的时间复杂度：

1、归并操作的工作原理包括申请空间使其大小为两个已经 排序序列之和，该空间用来存放合并后的序列，设定两个指针最初位置分别为两个已经排序序列的起始位置，比较两个指针所指向的元素，选择相对小的元素放入到合并空间并移动指针到下一位置，重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾。

2、归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用，将已有序的子序列合并得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序，若将两个有序表合并成一个有序表称为二路归并。

3、按数量级递增排列，常见的时间复杂度有常数阶O(1)对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2n)，平方阶O(n2)，立方阶O(n3)，……k次方阶O(nk)指数阶O(2n)，随着问题规模n得不断增大。

归并排序和快速排序的区别：

1、先分解再合并：归并排序先递归分解到最小粒度，然后从小粒度开始合并排序，自下而上的合并排序;

2、边分解边排序：快速排序每次分解都实现整体上有序，即参照值左侧的数都小于参照值，右侧的大于参照值;是自上而下的排序;

3、归并排序不是原地排序，因为两个有序数组的合并一定需要额外的空间协助才能合并;

4、快速排序是原地排序，原地排序指的是空间复杂度为O(1);

5、归并排序每次将数组一分为二，快排每次将数组一分为三

标签： 有效排序算法 分治法典型应用 二路归