自底向上的归并排序算法

自底向上的归并排序算法是一种经典的排序算法，它采用了迭代的方式进行排序。下面是该算法的步骤：

1. 将待排序的数组分割成若干个长度为1的子数组。
2. 将相邻的子数组进行合并，得到长度为2的有序子数组。
3. 重复步骤2，直到得到一个完全有序的数组。

具体实现时，可以使用一个辅助数组来存储合并的结果，然后再将结果复制回原数组。每次合并时，需要比较两个子数组的元素，并按照从小到大的顺序将它们放入辅助数组中。

以下是自底向上归并排序算法的伪代码：

MergeSort(arr):
    n = arr.length
    aux = new Array(n)  // 辅助数组

    // 子数组大小从1开始，逐渐增加
    for size = 1 to n-1 step size*2:
        // 合并相邻的子数组
        for i = 0 to n-1 step size*2:
            // 计算子数组的边界
            low = i
            mid = i + size - 1
            high = min(i + size*2 - 1, n-1)

            // 合并子数组
            merge(arr, aux, low, mid, high)

// 合并两个有序子数组
merge(arr, aux, low, mid, high):
    i = low
    j = mid + 1
    k = low

    // 比较两个子数组的元素，并按顺序放入辅助数组
    while i <= mid and j <= high:
        if arr[i] <= arr[j]:
            aux[k] = arr[i]
            i = i + 1
        else:
            aux[k] = arr[j]
            j = j + 1
        k = k + 1

    // 将剩余的元素复制到辅助数组
    while i <= mid:
        aux[k] = arr[i]
        i = i + 1
        k = k + 1

    while j <= high:
        aux[k] = arr[j]
        j = j + 1
        k = k + 1

    // 将辅助数组的结果复制回原数组
    for i = low to high:
        arr[i] = aux[i]