6、数据结构与算法——归并排序（2） - liuxiaofei2010S/special-column GitHub Wiki

上一篇写了自顶而下的归并排序，现在表述一下自底向上的归并排序。即第一层是数组项为1的两组数组排序，第二层为2的数组排序，以此类推，一直到最顶层的两个数组归并。

代码如下：

public static void sort(int[] array) {
    int N = array.length;
    for (int i = 1; i < N; i *= 2) {
        for (int k = 0; k < N - i; k++) {             // mid最大只能为最后第二项
            merge(array, k, k + i - 1, Math.min(k + i * 2 - 1, N - 1));
        }
    }
}

自底向上的归并排序需要 1/2NlgN 到 NlgN 的比较次数，最多访问数组 6NlgN 次。

比较适合链表式的数据结构排序。