问题

2.2.3
Answer Exercise 2.2.2 for bottom-up merge sort.
用自底向上的归并排序解答练习2.2.2

解析：

排序过程如下：

size =  1, merge(a,  0,  0,  1) A   E   Q   S   U   Y   E   I   N   O   S   T   
size =  1, merge(a,  2,  2,  3) A   E   Q   S   U   Y   E   I   N   O   S   T   
size =  1, merge(a,  4,  4,  5) A   E   Q   S   U   Y   E   I   N   O   S   T   
size =  1, merge(a,  6,  6,  7) A   E   Q   S   U   Y   E   I   N   O   S   T   
size =  1, merge(a,  8,  8,  9) A   E   Q   S   U   Y   E   I   N   O   S   T   
size =  1, merge(a, 10, 10, 11) A   E   Q   S   U   Y   E   I   N   O   S   T   
size =  2, merge(a,  0,  1,  3) A   E   Q   S   U   Y   E   I   N   O   S   T   
size =  2, merge(a,  4,  5,  7) A   E   Q   S   E   I   U   Y   N   O   S   T   
size =  2, merge(a,  8,  9, 11) A   E   Q   S   E   I   U   Y   N   O   S   T   
size =  4, merge(a,  0,  3,  7) A   E   E   I   Q   S   U   Y   N   O   S   T   
size =  8, merge(a,  0,  7, 11) A   E   E   I   N   O   Q   S   S   T   U   Y   

思路：

归并排序的另一种实现是自底下上的方法。
第一遍先将size=1的子数组排序，然后在此基础上对size=2的子数组排序，以此类推。

image.png

代码实现：

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) {
      for (int lo = 0; lo < N - sz; lo += sz + sz) {
        merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
      }
    }
    assert isSorted(a);

  }

具体执行过程：

image.png