基本思路
将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。
最基本的算法——归并操作
归并：一个集合前半部分有序，后半部分也有序，现在通过归并的手段让整体有序
基本算法：依次从两个集合中取数据，谁小谁放前面
private static void mergeArray1(Comparable[] a, int start, int middle, int end) {
Comparable[] temp = new Comparable[end - start + 1];
int i = start;
int j = middle + 1;
int k = 0;
while ((i <= middle) && (j <= end)) {
if (less(a[i], a[j])) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
while (i <= middle) {
temp[k++] = a[i++];
}
while (j <= end) {
temp[k++] = a[j++];
}
System.arraycopy(temp, 0, a, start, end - start + 1);
}
我们可以看到归并操作，需要创建一个临时集合来存放有序数据，最后再把数据copy回原集合。归并操作在归并排序中是需要递归调用的，频繁的new 集合不合理。
原地归并的方案
我们希望能够尽可能的原地归并数据，当然不可能完全实现。一个可行的方案是：排序前建一个和原数组大小相等的辅助数组，在每一次merge操作时，将对应的数据先copy过来，然后将数据从辅助数组排序到输入数组。
private static void mergeArray2(Comparable[] a, int start, int middle,
int end, Comparable[] temp) {
int i = start;
int j = middle + 1;
int k = start;
System.arraycopy(a, start, temp, start, end - start + 1);
while ((i <= middle) && (j <= end)) {
if (less(temp[i], temp[j])) {
a[k++] = temp[i++];
} else {
a[k++] = temp[j++];
}
}
while (i <= middle) {
a[k++] = temp[i++];
}
while (j <= end) {
a[k++] = temp[j++];
}
}
我们看到mergeArray2和mergeArray1最大的区别就是：
mergeArray1归并动作在辅助数组中完成，辅助数组完成归并后，再arrayCopy回原数组。
而直接mergeArray2在原数组中归并。也就是所谓的原地归并。
自顶向下的归并排序（递归）
上面我们已经有了基本的归并算法，那么归并排序也就很清晰了：
1.找到数组的middle
2.递归的对上半部分排序，递归的对下半部分排序
3.归并操作
几个注意的点：
- 当递归到一定程度，数组元素已经比较少的时候，可以使用插入或者选择排序进行排序
- 由于上下两部分都是有序数组，当恰好a[middle]<a[middle+1]时，就可以认为已经是有序的。
public static void merge_sort(Comparable[] a) {
Comparable[] temp = new Comparable[a.length];
mergesort(a, 0, a.length - 1, temp);
}
private static void mergesort(Comparable[] a, int start, int end,
Comparable[] temp) {
if (end - start + 1 < 15) { //小于15的数据，可以采用插入或者选择排序
select_sort(a, start, end);
} else {
int middle = (start + end) / 2;
if (start < end) {
mergesort(a, start, middle, temp);
mergesort(a, middle + 1, end, temp);
if (!less(a[middle], a[middle + 1])) { //如果a[middle]< a[middle + 1],我们认为已经有序
mergearray(a, start, middle, end, temp);
}
}
}
}
自底向上的归并排序（非递归，适合链表）
既然有递归的方案，那反过来一定有非递归的方案。
方案：归并微型数组，然后成对归并得到的子数组，直到将整个数组归并到一起。
- mergeArray(0,0,1) mergeArray(2,2,3)—— mergeArray(0,1,3)
- mergeArray(0,1,3) mergeArray(4,5,7)—— mergeArray(0,3,7)
- mergeArray(0,3,7) mergeArray(8,11,15)
- 如此反复，直到合并为一个大小为N的数组
private static void mergeBU_sort(Comparable[] a) {
Comparable[] temp = new Comparable[a.length];
int N = a.length;
for (int sz = 1; sz < N; sz = sz + sz) { // sz为每次归并的数组长度，从1开始，一直到N/2
for (int start = 0; start < N - sz; start += sz + sz) { // 对每一个数组进行mergearray操作
int middle = start + sz - 1;
int end = start + sz - 1 + sz;
mergearray(a, start, middle,
Math.min(end, N - 1), temp);
}
}
}
