自底向上归并排序

要求

给定一个无序的数组，要求使用自底向上的方法将数据进行从大到小的排序。

举例：

int[] A = {2,3,6,9,5,8};   //6个元素
A = {2,3,5,6,8,9};         //排序后的结果

//排序过程
//1. 将元素分成6组
//A：2  3  6  9  5  8
//2. 每两个两个地合并为一组
//A：2,3 6,9 5,8
//3. 每两组再合并为新的一组
//A：2,3,6,9 5,8
//4. 重复以上步骤，发现只剩一个组，排序完成
//A：2,3,5,6,8,9

基本思路

该算法需要分成两个步骤：拆分和归并，如果使用递归的方法，则拆分可以在递归时完成，即如果数组的长度不为1，就继续拆分下去。

而如果使用自底向上方法的话，需要时刻跟踪当前存在的组数，每个组所含的元素的数量；归并方法可以使用另外的函数来实现。

//伪代码
//先实现合并方法
merge(A[], startOfFirst, endOfFirst, endOfSecond){
    B[endOfSecond - startOfFirst + 1];     //辅助数组
    int index1, index2,indexOfB;
    index1 = startOfFirst;
    index2 = endOfFirst + 1;
    indexOfB = 0;
    while(index1 <= endOfFirst && index2 <= endOfSecond){
        if(A[index1] > A[index2]){
            B[indexOfB] = A[index2];
            index2++;
        } else {
            ...
        }
        indexOfB++;
    }
    if(index1 > endOfFirst){  //后一个数组的元素还没有遍历完
        while(index2 <= endOfSecond){
            B[indexOfB] = A[index2];
            indexOfB++;index2++;
        }
    } else {
        ...
    }
    index1 = startOfFirst;
    index2 = 0;
    for(;index2 < B.length; index2++, index1++){
        A[index1] = B[index2];
    }
    return;
}


//实现自底向上排序
bottomUpSort(A[]){
    //A的最大长度，当前每组的大小，合并后的新组的最大长度
    //当组的长度超过或者等于A的长度时，结束循环
    length = A.length;
    currentSize = 1;
    nextSize = currentSize * 2;
    index = 0
    while(currentSize < length){
        for(index = 0; index + nextSize - 1 < length; index += nextSize){
            merge(index, index + currentSize - 1, index + nextSize - 1);
        }
        //考虑length%nextSize > currentSize
        if(...){
            merge(index, index + currentSize - 1, length - 1);
        }
        currentSize = nextSize;
        nextSize = currentSize * 2;
    }
    return;
}