合并排序

归并排序是另一种排序算法，属于分而治之技术的范畴。 它是成功构建递归算法的最佳排序技术之一。

分而治之策略

在这种技术中，我们将一个问题分成两半并分别解决。 在找到每一半的解决方案后，我们将它们合并回去以表示主要问题的解决方案。

假设我们有一个数组A，那么我们主要关注的是对子部分进行排序，该子部分从索引p开始，到索引r结束，用A[p..r]表示。

除以

如果假设q是介于p和r之间的某个中心点，那么我们将把子数组A[p..r]分割成两个数组A[p..q]和A[q+1, r]。

征服

将数组分成两半后，下一步就是征服。 在此步骤中，我们单独对两个子数组A[p..q]和A[q+1, r]进行排序。 如果我们没有到达基本情况，那么我们再次遵循相同的过程，即，我们进一步分割这些子数组，然后分别对它们进行排序。

合并

当征服步骤获得基本步骤时，我们成功获得了排序后的子数组A[p..q]和A[q+1, r]，之后我们将它们合并回去以形成新的排序数组[p..r]。

归并排序算法

MergeSort 函数不断将数组分成两半，直到满足尝试对大小为 1 的子数组执行 MergeSort 的条件，即p == r。

然后，它将单独排序的子数组组合成更大的数组，直到合并整个数组。

在这里，我们调用MergeSort(A, 0, length(A)-1)来对整个数组进行排序。

正如您在下面给出的图像中看到的，归并排序算法递归地将数组分成两半，直到满足基本条件，即我们只剩下数组中的 1 个元素。 然后，merge 函数拿起排序后的子数组并将它们合并回来以对整个数组进行排序。

下图说明了分割（拆分）过程。

归并排序的合并步骤

主要的递归算法依赖于基本情况以及将其从基本情况得出的结果合并回来的能力。 归并排序没有什么不同的算法，只是这里的merge步骤具有更重要的意义。

对于任何给定的问题，合并步骤都是一种解决方案，它将两个单独排序的列表（数组）组合起来以构建一个大的排序列表（数组）。

归并排序算法支持三个指针，即，一个用于两个数组，另一个用于保留最终排序数组的当前索引。

Merge() 函数分步解释

考虑以下未排序数组的示例，我们将借助归并排序算法对其进行排序。

A= (36,25,40,2,7,80,15)

步骤 1： 归并排序算法迭代地将数组分成相等的两半，直到我们获得一个原子值。 如果数组中存在奇数个元素，那么其中一半将比另一半具有更多元素。

步骤 2： 将数组分成两个子数组后，我们会注意到它不会妨碍元素在原始数组中的顺序。 从现在开始，我们将进一步将这两个数组分成其他两半。

步骤 3： 同样，我们将分割这些数组，直到我们获得一个原子值，即，一个不能进一步分割的值。

步骤 4： 接下来，我们将以与它们被分解时相同的方式将它们合并回来。

步骤 5： 对于每个列表，我们将首先比较元素，然后将它们组合起来以形成新的排序列表。

步骤 6： 在下一次迭代中，我们将比较两个数据值的列表，并将它们合并回找到的数据值的列表，所有数据值都以排序方式放置。

因此，数组已排序。

归并排序的分析

令 T (n) 为归并排序算法所花费的总时间。

• 对两半进行排序最多需要 2T时间。
• 当我们合并排序后的列表时，我们会得到一个总的 n-1 比较，因为剩下的最后一个元素需要在组合列表中复制下来，并且不会有任何比较。

因此，关系公式为

但是我们忽略'-1'，因为该元素需要一些时间才能复制到合并列表中。

因此 T (n) = 2T+ n...公式 1

注意：停止条件 T (1) =0，因为最后，只剩下 1 个需要复制的元素，并且不会有任何比较。

将 2 方程代入 1 方程

将 4 方程代入 3 方程

从停止条件

两边都应用 log

log n=log₂i
logn= i log2
=i

log₂n=i

从第 6 方程

最佳情况复杂度： 对于已经排序的数组，归并排序算法的最佳情况时间复杂度为 O(n*log n)。

平均情况复杂度： 归并排序算法的平均情况时间复杂度为 O(n*log n)，当 2 个或更多个元素被打乱时发生，即既不是升序也不是降序。

最坏情况复杂度： 最坏情况时间复杂度也是 O(n*log n)，当我们按升序对数组的降序进行排序时会发生这种情况。

空间复杂度： 归并排序的空间复杂度为 O(n)。

归并排序应用

归并排序的概念适用于以下领域

• 反转计数问题
• 外部排序
• 电子商务应用