思路分析
归并排序：是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使 子序列段间有序。
图解
代码示例
1）递归方法
代码语言：javascript复制//有两个重要的特点，可以适用于外部排序（数据在磁盘上），也可以适用于链表排序
// （希尔，堆排序，快速排序依赖随机访问能力，都不适合链表排序）
//基本思路来源于基本问题：把两个有序链表/数组合并成一个
//[low,mid) 有序区间
//[mid,high) 有序区间
//两个区间进行合并
public static void merge(int[] array,int low, int mid, int high){
int[] output = new int[high - low];
int outputIndex = 0;//记录当前output数组中被放入了多少元素
int cur1 = low;//第一个区间的起始下标
int cur2 = mid;//第二个区间的起始下标
while (cur1 < mid && cur2 < high){
//以下条件写成小于等于，才能保证稳定性
if (array[cur1] <= array[cur2]){
output[outputIndex] = array[cur1];
outputIndex ;
cur1 ;
}else {
output[outputIndex] = array[cur2];
outputIndex ;
cur2 ;
}
}
//当以上循环结束的时候，肯定有一个cur到达末尾，另一个还剩下一些内容
//把剩余的内容老被到output中
while (cur1 < mid){
output[outputIndex] = array[cur1];
outputIndex ;
cur1 ;
}
while (cur2 < high){
output[outputIndex] = array[cur2];
outputIndex ;
cur2 ;
}
//把output的元素搬运到原来的数组
for (int i = 0; i < high - low; i ){
array[low i] = output[i];
}
}
public static void mergeSort(int[] array){
mergeSortHelper(array,0,array.length);
}
//[low,high)前闭后开区间
private static void mergeSortHelper(int[] array, int low, int high) {
if (high - low <= 1){
return;
}
int mid = (low high) / 2;
mergeSortHelper(array,low,mid);
mergeSortHelper(array,mid,high);
//当我们把左右区间归并排序完了，说明左右区间已经是有序区间了
merge(array,low,mid,high);
}2）非递归方法
代码语言：javascript复制public static void mergrSortByLoop(int[] array){
//引入一个gap变量进行分组
//当gap为1的时候，0 1是一组 2 3是一组 4 5是一组。。。
//当gap为2的时候，就是[0，1]和【2，3】是一组。。。。
//当gap为4的时候，【0，1，2，3】和【4，5，6，7】是一组
for (int gap = 1; gap < array.length; gap *= 2){
//接下来进行具体的分组合并
for (int i = 0; i < array.length; i = 2*gap){
int beg = i;
int mid = i gap;
int end = i 2*gap;
//防止下标越界
if (mid > array.length){
mid = array.length;
}
if (end > array.length){
end = array.length;
}
merge(array,beg,mid,end);
}
}
}性能分析
时间复杂度： O(n * log(n))
空间复杂度： O(n)
稳定性： 稳定排序
