概要

归并排序就是将一个数组分成前后两部分，分别排序，最后将结果归并起来，形成一个有序的新数组。

• 优点：数组排序所需时间与数组长度关系：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]左右部分合并。。。。轨迹图如图一所示：

  
  
  图一：自顶向下的归并排序的调用轨迹

未完待续