2.2 归并排序 Merge Sort

• 要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。
• 归并排序最吸引人的性质是它能够保证将任意长度为 N 的数组排序所需时间 和 NlogN 成正比；它的主要缺点则是它作序的额外空间和 N 成正比。
• 归并排序处理数百万甚至更大规模的数组（这是插入排序或者选择排序做不到的）
• 主要缺点是铺筑数组所使用的额外空间和 N 的大小成正比

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] 复制到 auk[lo..hi]
        auk[k] = a[k];
    }
    for(int k = lo; k <=hi; k++){ // 归并回到 a[lo..hi]
        if      (i > mid)                   a[k] = auk[j++];
        else if (j > hi)                    a[k] = auk[i++];
        else if (less(auk[j], auk[i]))      a[k] = auk[j++];
        else                                a[k] = auk[i++];
    }
}

    def _merge(self, array, lo, mid, hi):
        i, j = lo, mid + 1
        for k in range(k, hi + 1):
            self.aux.insert(k, array[k])  # 将 array[lo..hi] 复制到 aux[lo..hi]
        for k in range(lo, hi + 1):  # 归并回到 array[lo..hi]
            if i > mid:
                array[k] = self.aux[j]
                j+=1
            elif j > hi:
                array[k] = self.aux[i]
                i+=1
            elif self.aux[j] < self.aux[i]:
                array[k] = self.aux[j]
                j+=1
            else:
                array[k] = self.aux[i]
                i+=1

sort() 方法的作用启示在于安排多次 merge() 方法调用的正确顺序

自顶向下的归并排序

public class Merge{
    private static Comparable[] aux;  // 归并所需的辅助数组
    public static void sort(Comparable[] a){
        aux = new Comparable[a.length]; // 一次性分配空间
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi){
        //将数组a[lo..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); // 归并结果
    }
}

class Merge(object):
    """docstring for Merge"""
    def __init__(self):
        self.aux = []  # aux 归并所需的辅助数组

    def _merge_sort(self, array, lo, hi):
        # 将数组a[lo..hi]排序
        if hi <= lo: return
        int mid = lo + (hi - lo) / 2
        self._merge_sort(array, lo, mid)  # 将左半边排序
        self._merge_sort(array, mid + 1, hi)  # 将右半边排序
        self._merge(array, lo, mid, hi)  # 归并结果
    
    def merge_sort(self, array):  
        self._merge_sort(array, 0, len(array) - 1)

自底向上的归并排序

递归实现的归并排序是算法设计中分治思想的典型应用。
将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。
实现归并排序的另一种方法是先归并那些微型数组，然后在承兑归并得到的字数组，知道我们将整个数组归并在一起。这种实现方法比标准递归方法所需要的代码量更少。

public class MergeBU{
    private static Comparable[] aux;  // 归并所需的辅助数组
    public static void sort(Comparable[] a){
        int N = a.length;
        aux = new Comparable[N];
        for(int sz = 1; sz < N; sz = sz + sz){  // sz 子数组大小
            for(int lo = 0; lo < N - sz; lo += sz + sz){  // lo: 子数组索引
                merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
            }
        }
    }
}

当数组长度为 2 的幂时，自顶向下和自底向上的的归并排序所用的比较次数和数组访问次数正好相同，只是顺序不同。

自底向上的归并排序比较适合用链表组织的数据。这种方法只需要重新组织链表链接就能将链表原地排序（不需要创建任何新的链表结点）。