传统归并排序先递归把原数组拆为子数组，然后对子数组进行合并。还有一种归并排序不需要先拆分，直接对子数组进行合并得到最后的有序数组。
程序如下
public class ButtomUpMergeSort extends MergeSortImproved {
// merge method is inherited from superclass
// override sort method
public static void sort (Comparable[] a) {
int n = a.length;
aux = new Comparable[n]; // aux: a blank array inherited from superclass
for (int sz = 1; sz < n; sz = sz + sz) {
for (int low = 0; low < n - sz; low += sz + sz) {
merge(a, low, low + sz - 1, Math.min(low + sz + sz - 1, n - 1));
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer[] test = new Integer[] {2, 4, 5, 1, 11, 7, 9, 6, 10, 8, 3};
sort(test);
show(test);
}
}
这里继承的merge方法可以参见之前文章https://blog.csdn.net/Raine_Yang/article/details/120604140
程序说明：
外循环：sz为每次归并的元素个数，从1开始，直到归并数量达到整个数组，每一轮归并后把sz翻倍
内循环：遍历整个数组，按照每（sz）个元素的子数组进行归并，如果数组剩余元素个数小于sz，则直接归并剩余所有元素
