一.合并排序介绍将两个有序数列合并为一个有序数列称为“合并”。
合并排序(Merge Sort )是利用合并思想对数列进行排序。 根据具体实现，合并排序有“从上到下”和“从下到上”两种方式。
自下而上合并排序：将待排序的数列分成若干长度为1的子数列，并将这些数列各合并两个； 得到几个长度为2的规则数列，将这些数列合并为两个； 得到几个长度为4的规则数列，将它们合并成两个； 直到直接合并成一个数列。 这样就得到了我们想要的排名结果。 (见下面的照片)
从上到下合并排序：从下到上的排序方向与从上到下的排序方向相反。 基本上有三个步骤。
分解将当前区间分为两部分，即求分裂点mid=(lowhigh )/2；
求解递归合并排序两个子区间a[low…mid]和a[mid 1…high]。 递归的结束条件是子区间的长度为1。
合并将已排序的两个子区间a[low…mid]和a[mid 1…high]合并为一个有序区间a[low…high]。
下面的照片清楚地反映了“从下而上”和“从上到下”合并排序的差异。
二、合并排序字符串说明合并排序(自上而下)代码
/* *将两个相邻数组中的两个有序区间合并为一个* *参数说明： * a --包含两个有序区间的数组* start --第二个有序区间的起始地址。 * mid --第一个有序区间的结束地址。 也是第二个有序区间的起始地址。 *结束- -第一个有序区间的结束地址。 * /语音合并(int )、int start、int mid、int end ) int*tmp=(int* ) malloc ) (end-start1) * sizeof (int ) )； //tmp是由两个有序区域组成的临时区域int i=start；//第一个有序区域的索引int j=mid 1；//第二个规则区域的索引int k=0； //临时区域索引while(I=midj=end ) if ) a[I]=a[j] ) tmp[k ]=a[i ]； else tmp[k ]=a[j ]； }while(I=mid ) tmp[k ]=a[i ]； while(j=end ) tmp[k ]=a[j ]； //将所有已排序的元素组合到数组a中。 for(I=0； i k； I ) a [开始I ]=tmp [ I ]； 自由(tmp； }/* *合并排序(从上到下) *参数说明(a--要排序的数组) *开始- -数组的起始地址) * endi --数组的结束地址(/void merge _ sort _ up 2 merge_sort_up2down(a，start，mid )； //递归排序a [ start . mid ] merge _ sort _ up2 down (a，mid 1，end )； //递归排序a[mid 1.end] //a[start.mid]和a[mid.end]是两个有序空间，//将它们划分为一个有序空间a[start.end]merge(a，mid . end )
数组{80、30、60、40、20、10、50、70}可能由两个规则的子数组{80、30、60、40}和{20、10、50、70}组成。 只需对两个有序子树组进行排序。 子数组{80、30、60、40}被认为由两个规则的子数组{80、30}和{60、40}组成。
假设子数组{20、10、50、70}由两个有序的子数组{20、10}和{50、70}组成。 假设子数组{ 80，30 }由两个有序的子数组{80}和{30}组成。
假设子数组{ 60，40 }由两个有序的子数组{60}和{40}组成。
假设子数组{ 20，10 }由两个有序的子数组{20}和{10}组成。
假设子数组{ 50，70 }由两个有序的子数组{50}和{70}组成。 合并排序(自下而上)代码
/*合并几次数组a。 序列a全长为len，将其分为几个长度为gap的子序列； *对“每两个相邻子数组”进行合并排序。 *参数说明： * a --要排序的数量
组 * len -- 数组的长度 * gap -- 子数组的长度 */void merge_groups(int a[], int len, int gap){ int i; int twolen = 2 * gap; // 两个相邻的子数组的长度 // 将"每2个相邻的子数组" 进行合并排序。 for(i = 0; i+2*gap-1 < len; i+=(2*gap)) { merge(a, i, i+gap-1, i+2*gap-1); } // 若 i+gap-1 < len-1，则剩余一个子数组没有配对。 // 将该子数组合并到已排序的数组中。 if ( i+gap-1 < len-1) { merge(a, i, i + gap - 1, len - 1); }}/* * 归并排序(从下往上) * * 参数说明： * a -- 待排序的数组 * len -- 数组的长度 */void merge_sort_down2up(int a[], int len){ int n; if (a==NULL || len<=0) return ; for(n = 1; n < len; n*=2) merge_groups(a, len, n);}从下往上的归并排序的思想正好与"从下往上的归并排序"相反。如下图：
通过"从下往上的归并排序"来对数组{80,30,60,40,20,10,50,70}进行排序时：
小编推荐自己的linuxC/C++语言技术交流群:【1106675687】整理了一些个人觉得比较好的学习书籍、视频资料共享在群文件里面，有需要的可以自行添加哦！
归并排序时间复杂度
归并排序的时间复杂度是O(NlgN)。
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？
归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(NlgN)。
归并排序稳定性
归并排序是稳定的算法，它满足稳定算法的定义。
算法稳定性 – 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！
下面给出归并排序的三种实现：C、C++和Java。这三种实现的原理和输出结果都是一样的，每一种实现中都包括了"从上往下的归并排序"和"从下往上的归并排序"这2种形式。
归并排序C实现
实现代码(merge_sort.c)
归并排序C++实现
实现代码(MergeSort.cpp)
归并排序Java实现
实现代码(MergeSort.java)
上面3种实现的原理和输出结果都是一样的。下面是它们的输出结果：
before sort:80 30 60 40 20 10 50 70 after sort:10 20 30 40 50 60 70 80