Algorithms, Part I 5-Mergesort

HC_Plantern

March 21 2023

算法数据结构

5-Mergesort

插入排序

基本做法

将数组分成两半
递归地对这两部分排序
将已排好序的两部分合并

合并的代码实现

    // stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
        assert isSorted(a, lo, mid);
        assert isSorted(a, mid+1, hi);

        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k]; 
        }

        // merge back to a[]
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)              a[k] = aux[j++];
            else if (j > hi)               a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else                           a[k] = aux[i++];
        }

        // postcondition: a[lo .. hi] is sorted
        assert isSorted(a, lo, hi);
    }

排序过程中的状态如下图

完整代码实现

public class Merge {

    private static void merge(...) {
        // as before
    }

    // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     * @param a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length-1);
        assert isSorted(a);
    }
}

大致排序过程如下图

复杂度分析

空间：

一个长度为 $n$ 的数组

时间：

对于两个长度为 $n$ 的数组进行合并需要 $\leq6n$ 次操作
递归树一共有 $log_2n+1$ 层
对于第 $j$ 层（从0开始计数），一共有 $2^j$ 个需要递归的数组，其中两个一组。每组数组的长度为 $\frac{n}{2^j}$
因此，每一层所需要的操作数 $\leq2^j*6(\frac{n}{2^j})=6n$ ，总计 $6n(log_2n+1)$ 次操作

以下是证明相关图片

注意这里的每一个圈圈代表的是两个数组merge的过程

改进方案

对于小数组采用插入排序：规模较小时插入排序相较于归并排序的效率更高，开销更少。
如果已经排好序，就取消合并的操作：检查左半部分最大的元素是否比右半部分最小的元素要小
避免辅助数组的复制操作：每次归并时交换原数组与辅助数组的参数位置，以此规避了每次合并时都要将元素复制到辅助数组的操作，节省时间。

迭代的插入排序

将递归改成迭代

代码如下：

public class MergeBU {


    // stably merge a[lo..mid] with a[mid+1..hi] using aux[lo..hi]
    private static void merge(...) {
        // as before
    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     * @param a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        int n = a.length;
        Comparable[] aux = new Comparable[n];
        for (int len = 1; len < n; len *= 2) {
            for (int lo = 0; lo < n-len; lo += len+len) {
                int mid  = lo+len-1;
                int hi = Math.min(lo+len+len-1, n-1);
                merge(a, aux, lo, mid, hi);
            }
        }
        assert isSorted(a);
    }