mergesort,mergesort空间复杂度

归并排序中算法MergeSort（）是怎么回事？

-MergeSort(R,low,mid);和MergeSort(R,mid+1,high);是对R（low...mid）和R（mid+1...high）进行排序吗？？

不是排序，而是分裂。分别对左右两边进行折半分裂，直到只剩下一个元素。归并排序是Divide and Conquer算法，分裂+合并。先递归调用MergeSort分裂直至只剩一个元素，然后调Merge辅助函数合并两个有序数组（只有一个元素的数组也是有序数组）。

-我怎么认为只是把例如R(N)={0,1,3,2}，最终分解为0,1,3,2呢？？

的确先是分成单个元素的，然后{0}与{1}两个数组通过Merge合并成为{0, 1}；{3}与{2}两个数组合并成{2, 3}。然后退到递归上一层，调Merge合并{0, 1}和{2, 3]两个有序数组为{0, 1, 2, 3}。

归并排序的思想就是每次合并两个有序数组。

再举个例子：{5, 3, 6, 1}。

MergeSort分裂为{5, 3}和{6, 1}

MergeSort分裂{5, 3}为{5}, {3}；分裂{6, 1}为{6}, {1}

现在递归已经到头，因为继续分的话lowhigh

所以运行Merge，合并{5}, {3}为{3, 5}；合并{6}, {1}为{1, 6}

退到上一层递归，合并{3, 5}和{1, 6}为{1, 3, 5, 6}。

其实真正的排序步骤是在Merge里：怎样合并两个有序数组。

大数据中的归并排序(Merge Sort)

最近在研究大数据的分治思想，很多场景计算得出的中间结果都是“内部有序，外部无序”，这时候就要用到“归并排序”算法将多个这样的结果集合归并为一个有序的集合。于是就复习了一下“归并排序”。

在大数据场景中，数据量远大于计算机的内存，磁盘和网络的IO又是无法解决的瓶颈，就需要用到分治思想。

比如有1000G的中国2020年某电商平台用户消费总金额数据。数据格式是用户名：消费总金额。所有数据都是无序的。现在有1台磁盘5T/内存8G（程序可用内存约为5G多）的计算机。如何将数据按消费总金额从大到小排序输出？

a. 从有序队列中取出第一个元素。

b. 将此元素数据写入输出的文件中，并从此元素所属的数组中的下一个元素放入有序队列。

c. 重复步骤a，b直到某个数组元素耗尽，从这个数组所属的5G文件中，继续加载25M数据到内存中。

d. 重复步骤a，b，c直到所有5G文件的数据全部加载到内存中，并写入到输出文件。

Arrays.mergeSort() 解析

Arrays 在对 Object 数组进行排序是会使用到 legacyMergeSort 和 ComparableTimSort.sort

其中 legacyMergeSort 调用的就是 mergeSort 方法

来看看 mergeSort 的具体实现。

迭代的时候每次都选择当前 index 后面最大的元素进行交互位置

以一个 length 为 16 的数组举例,大致解释一下 mergeSort 排序:

调用 mergeSort 方法时 length 为 16, 因为 length 为 8 不满足插入排序的条件， 此时将数组分为两半:

数组1的 index 范围为: [0, 8)

数组2的 index 范围为: [8, 16)

继续看数组1: 对数组以递归调用, 因为 length 为 8 不满足插入排序的条件，此时将数组1分为 2 半:

数组1_1, index 范围为: [0, 4)

此时满足 length 7 的条件, 进行插入排序

数组1_2, index 范围为: [4, 8)

此时也满足 length 7 的条件, 进行插入排序

此时 数组1_1 和 数组1_2 都是局部有序的, 然后下一步会判断 数组1_1 的最大值与 数组1_2 的最小值之间的关系, 如果 max(数组1_1) = min(数组1_2) 则说明 数组1_1 + 数组1_2 也是有序的的,

否则对 数组1_1 和 数组1_2 进行2-路归并排序，最终得到的结果是 数组 index 为[0, 8) 的数据都是有序的

对数组2 进行两次递归调用后，数组 index 为[8, 16) 的数据都是有序的，判断数组1 的最大值和数组2 的最小值之间的关系, 如果 max(数组1) = min(数组2)，则说明 数组1 + 数组2 也是有序的的,

否则对 数组1 和 数组2 进行 2-路归并排序得到最终结果

以上就是 mergeSort 排序的全部过程了

归并排序（Merge Sort）

归并排序 是最高效的排序算法之一。该排序算法的时间复杂度是 O(log n) ，归并排序是由分割和合并组成的。将一个比较大的问题分割成若干容易解决的小问题，然后进行合并，得到一个最终的结果。归并排序的口诀就是先分割，后合并。

举个例子，假定你手中有如下一摞卡牌：

mergeSort1.png mergeSort1.png

排序算法的排序过程大致是这样的：

1，首先，将这一摞牌分成两半，这样就得到了两摞无序的卡牌。

mergeSort2.png mergeSort2.png mergeSort3.png mergeSort3.png

1，最后，以和分割相反的顺序，将每一摞卡牌合并。在每一次合并的过程中，将数据按照规则进行排序。由于每一小摞的卡牌都已经有序，在合并的时候会比较容易些。

mergeSort4.png mergeSort4.png

首先，先将数组分成两半：

将数组分割一次远远不够，需要递归调用分割函数，直到不能在分割为止。这样的话，每一个子部分都只包含一个元素。按照这种思路，我们将 mergeSort 更新至如下所示：

这里有两个变动点：

1，对函数进行了递归调用，在数组中有且只有一个元素时，停止递归调用。

2，对原数组的左右子数组都调用 mergeSort 。

如上代码在能通过编译之前，仍然还有很多事情去做。现在已经完成了数组分割部分，是时候去关注于合并了。

合并左右子数组是该算法的最后一步。为了更算法更明了一些，单独创建一个 merge 方法。

merge 方法的职责仅仅是 将两个将两个有序的数组合并成一个有序的数组。在 mergeSort 函数中，增加以下方法：

最后附上本文的相关代码 DataAndAlgorim

参考链接 《Data Structures Algorithms in Swift》