归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide
and Conquer）的一个非常典型的应用。值得注意的是归并排序是一种稳定的排序方法。速度仅次于快速排序，为稳定排序算法，一般用于总体无序，但是各子项相对有序的数列。若将两个有序表合并成一个有序表，称为二路归并。
1、算法思想
比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。
归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
（1）分治法的三个步骤
设归并排序的当前区间是R[low..high]，分治法的三个步骤是：
①分解：将当前区间一分为二，即求分裂点
②求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序；
③组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。
递归的终结条件：子区间长度为1（一个记录自然有序）。
2、代码实现：
package sort;
public class MergingSort {
public static void main(String[] args) {
int[] a = {3, 2, 5, 4, 1};
sort(a, 0, a.length - 1);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
public static void sort(int[] data, int left, int right) {
if (left < right) {
// 首先找出中间的索引
int center = (left + right) / 2;
// 对左边的数组进行递归,使左边有序
sort(data, left, center);
// 对中间索引右边的数组进行递归，使右边有序
sort(data, center + 1, right);
// 再将二个有序数列合并
merge(data, left, center, right);
}
}
public static void merge(int[] data, int left, int center, int right) {
int[] tmpArr = new int[data.length];
int mid = center + 1;
// third记录中间数组的索引
int third = left;
int tmp = left;
while (left <= center && mid <= right) {
// 将两个数组中取出最小的数放入中间数组
if (data[left] <= data[mid]) {
tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
// 剩余部分依次放入中间数组
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
while (tmp <= right) {
data[tmp] = tmpArr[tmp++];
}
}
}
3、算法分析
1、稳定性
归并排序是一种稳定的排序。
2、存储结构要求
可用顺序存储结构。也易于在链表上实现。
3、时间复杂度
对长度为n的文件，需进行
lgn
趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
4、空间复杂度
需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。
注意：
若用单链表做存储结构，很容易给出就地的归并排序。
5、比较操作的次数介于(nlogn)
/ 2和nlogn - n + 1。
6、赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0 (n)
7、归并排序比较占用内存，但却是一种效率高且稳定的算法。
代码地址：https://github.com/zxiaofan/Algorithm/blob/master/src/sort/MergingSort.java