归并排序时间复杂度是什么?

Question

如题所述

Answer 1

归并排序(MERGE-SORT)时间复杂度是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

归并算法采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

其实现方式：先把待排序区间以中点二分； 接着把左边子区间排序； 再把右边子区间排序； 最后把左区间和右区间用一次归并操作合并成有序的区间。

合并排序又称为归并排序算法，是比较排序中时间复杂度最低的算法（已经理论证明）。也是充分利用了分治思想，分而治之，将复杂重复的工作不断进行分解至最小单元，而后逐层向上汇总，就像复杂的行政结构。