归并排序 是最高效的排序算法之一。该排序算法的时间复杂度是 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》
大数据中的归并排序(Merge Sort)
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 排序的全部过程了
归并排序中算法MergeSort（）是怎么回事？
最近在研究大数据的分治思想，很多场景计算得出的中间结果都是“内部有序，外部无序”，这时候就要用到“归并排序”算法将多个这样的结果集合归并为一个有序的集合。于是就复习了一下“归并排序”。
在大数据场景中，数据量远大于计算机的内存，磁盘和网络的IO又是无法解决的瓶颈，就需要用到分治思想。
比如有1000G的中国2020年某电商平台用户消费总金额数据。数据格式是用户名：消费总金额。所有数据都是无序的。现在有1台磁盘5T/内存8G（程序可用内存约为5G多）的计算机。如何将数据按消费总金额从大到小排序输出？
a. 从有序队列中取出第一个元素。
b. 将此元素数据写入输出的文件中，并从此元素所属的数组中的下一个元素放入有序队列。
c. 重复步骤a，b直到某个数组元素耗尽，从这个数组所属的5G文件中，继续加载25M数据到内存中。
d. 重复步骤a，b，c直到所有5G文件的数据全部加载到内存中，并写入到输出文件。
合并排序算法
-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}
现在递归已经到头，因为继续分的话low>high
所以运行Merge，合并{5}, {3}为{3, 5}；合并{6}, {1}为{1, 6}
退到上一层递归，合并{3, 5}和{1, 6}为{1, 3, 5, 6}。
其实真正的排序步骤是在Merge里：怎样合并两个有序数组。
//你没写递归边界
#include <stdio.h>
#include <stdlib.h>
void mergesort(int a[],int n)
void merge(int a[],int b[],int i,int c[],int j)
int main()
{
int a[20]={1,4,7,8,9,5,4,2,3,6,7,8,5,4,2,1,5,9,6,8},j
mergesort(a,20)
for(j=0j<20j++)
{
printf(”%d ”,a[j])
}
return 0
}
void mergesort(int a[],int n){
if(n<=1)
return//递归边界
int i,j
int *b
int *c
b=(int *)malloc(sizeof(int)*(n/2))
c=(int *)malloc(sizeof(int)*(n-n/2))
for(i=0i<n/2i++){
b[i]=a[i]
}
for(j=0j<n-n/2j++){
c[j]=a[j+n/2]
}
mergesort(b,(n/2))
mergesort(c,(n-n/2))
merge(a,b,(n/2),c,(n-n/2))
}
void merge(int a[],int b[],int x,int c[],int y)
{
int i=0
int j=0
int k=0
while((i<x)&&(j<y)){
if(b[i]<=c[j]){
a[k]=b[i]
i++
}
else{
a[k]=c[j]
j++
}
k++
}
int l
if(i==x){
for(l=jl<yl++){
a[k]=c[l]
k++
}
}
else{
for(l=il<xl++){
a[k]=b[l]
k++
}
}
}
以上就是关于归并排序（Merge Sort）全部的内容，如果了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！
更多相关资讯
