归并排序法（自下而上）
上一篇文章中简单介绍了归并排序，在二分的过程中使用了递归的设计，但我们还可以使用for循环的方式来对数组进行“二分”。
思路
这种归并排序就没有递出去二分的过程了，而是直接开始合并，因此也叫自底向上的归并排序，合并的过程并没有区别。
其实这可能比递归的归并排序更容易理解一些。
首先我们定义一个子数组长度gap，使用for循环让它从1开始成倍增长，这就是二分的逆过程。
然后在这个for循环中进行合并，在自上而下的归并排序中我们合并的两个子数组是arr[l, mid]和arr[mid+1, r]。
那么到了这里便成了arr[l, l+gap-1]和arr[l+gap, l+gap*2-1]。
可能这么说还是不太容易理解，我们直接看代码，我已经写满了注释。
实现
//自底向上的归并排序
void mergeSortBU(int arr[], int n) {
//gap可以理解为子数组长度，作为二分的逆过程，自然是从1开始成倍增长
for (int gap = 1; gap <= n; gap *= 2) {
//从数组左端开始，将两个子数组范围传给__merge合并，增量为两个子数组长度和即gap*2
//循环终止条件为i + gap < n，以免越界
for (int i = 0; i + gap < n; i += gap * 2) {
//当子数组长度小于某个点时改用插入排序
if (gap <= 15) {
insertionSort2(arr, i, i + gap * 2 - 1);
} else {
//当左侧子数组最后一个元素大于右侧第一个元素时才合并
if (arr[i + gap - 1] > arr[i + gap])
{
//注意右侧范围不能越界
__merge(arr, i, i + gap - 1, min(i + gap * 2 - 1, n - 1));
}
}
}
}
}
由于是自底向上的过程，因此这里要多注意越界的问题，将i+gap-1看成原本的mid应该有助于理解。
测试
随机数组
insertion sort2 : 1.810301s
merge sort : 0.008202s
merge sortBU : 0.008678s
近乎有序的数组
insertion sort2 : 0.001722s
merge sort : 0.001699s
merge sortBU : 0.002333s
可以看到自底向上的归并排序速度与自上而下的归并排序整体相当，稍慢一点点，但是自底向上的归并排序并不依赖数组下标取值，因此它也适用于链表的排序。