合并排序（归并排序）是一种高效的排序算法，可以产生稳定的排序，这意味着如果两个元素具有相同的值，则它们在排序序列中的相对位置与它们在输入中的相对位置相同。
换句话说，具有相等值的元素的相对顺序保留在排序序列中。合并排序是一种比较排序，这意味着它可以对定义了小于关系的任何输入进行排序。
与快速排序一样，合并排序是一种分治算法。它将输入数组分成两半，为这两半调用自身，然后合并两半。
上图来自维基百科，显示了示例数组 {38、27、43、3、9、82、10} 的完整合并排序过程。如果我们仔细看这个图，我们可以看到数组被递归地分成两半，直到大小变为 1。一旦大小变为 1，合并过程开始动作并开始合并数组，直到完整的数组合并。
归并排序的最坏情况时间复杂度是O(n.log(n))，其中n是输入的大小。递归关系为：
递归基本上总结了合并排序算法 - 对原始列表一半大小的两个列表进行排序，并添加n合并结果两个列表所采取的步骤。
归并排序算法所需的辅助空间是调用堆栈的O(n)。
对于较小的任务，与其他排序算法相比速度较慢。
合并排序算法需要额外的 0(n) 内存空间用于临时数组。
即使数组是已经排序过的，也会经历整个过程。
版权声明：本站部分内容来自互联网，仅供学习及演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，请提供相关证据及您的身份证明，我们将在收到邮件后48小时内删除。