概要
归并排序就是将一个数组分成前后两部分，分别排序，最后将结果归并起来，形成一个有序的新数组。
- 优点：数组排序所需时间与数组长度关系：NlogN
- 缺点：需要的额外空间与N成正比。原因：排好序的元素放到了新数组，就占用了额外的空间。
因此，如果归并一个很大的数组，进行多次归并时，由于每次归并都会创建一个新数组，那所占用的空间会很大，也会有好多麻烦。
原地归并
如果能在原地归并，不需要额外的空间的话，那就能解决上述问题。
- java代码：(将一个前后两部分分别有序的数组原地归并)
public static void merge(Comparable[] a, int lo, int mid, int hi)
{//将a[lo, mid]和a[mid + 1, hi]归并
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++)//首先将a[lo...hi]复制到aux[lo...hi]
aux[k] = a[k];
for (int k = lo; k <=hi; k++)//归并回到a[lo...hi]
if (i > mid) a[k] = aux[j++]; //左半边取尽就取右半边的元素
else if (i > mid) a[k] = aux[j++]; //右半边取尽就取左半边的元素
else if less(aux[j], aux[i])) a[k] = aux[j++];//两边都没有取尽就比较，把较小的取出来
else a[k] = aux[i++];
}
自顶向下的归并排序
对子数组a[l0...hi]排序，将它分为a[l0...mid]和a[mid+1...hi]两部分，分别地鬼调用他们单独排序，最后将有序的两个子数组归并为最终的排序结果。
- java代码
public class Merge
{
private static Comparable[] aux; //归并所需的辅助数组
public static void sort(Comparable[] a)
{
aux = new Comaparable[a.length];//一次性分配空间
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo)/2;
sort(a, lo, mid); //将左边排序
sort(a, mid+1, hi);//将右边排序
merge(a, lo, mid, hi);//归并结果
}
}
- 代码研究
归并排序的代码核心其实就是sort(Comparable[] a, int lo, int hi)函数不断的自我调用。 -
以a[0...15]为例
sort()方法调用自己将左半部分a[0...7]排序，再在其中调用自己将左半部分a[0...3]排序，再调用自己将a[0...3]左半部分a[0...1]排序。然后将a[0...3]右半部分a[2...3]排序，最后a[0...3]左右部分合并。。。。轨迹图如图一所示：
图一：自顶向下的归并排序的调用轨迹
