自底向上合并排序完整代码

自底向上合并排序（Bottom-up Merge Sort）也被称为迭代版本的归并排序，它的思想是从最小子序列开始，逐步合并成更大的子序列，直到整个数组有序。这种算法不需要递归，而是使用循环结构。

以下是一个Python的自底向上合并排序完整代码示例：

def merge_sort(arr):
    # 初始分治单位为一个元素
    if len(arr) <= 1:
        return arr

    # 使用临时数组进行合并操作
    temp = [None] * len(arr)

    # 当子数组长度大于1时，不断把大小为2^n的子数组两两合并
    size = 1
    while size < len(arr):
        for i in range(0, len(arr), size * 2):
            left = i
            mid = min(i + size - 1, len(arr) - 1)
            right = min(i + size * 2 - 1, len(arr) - 1)

            # 合并左右两个子数组
            merge(arr, temp, left, mid, right)
        size *= 2

    return arr


def merge(arr, temp, left, mid, right):
    # 指针从两端开始，找到合适的分割点
    i = left
    j = mid + 1
    k = left

    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            i += 1
        else:
            temp[k] = arr[j]
            j += 1
        k += 1

    # 把剩余未合并的部分复制到结果数组
    while i <= mid:
        temp[k] = arr[i]
        i += 1
        k += 1

    while j <= right:
        temp[k] = arr[j]
        j += 1
        k += 1

    # 将临时数组的内容回填到原数组
    for x in range(left, right + 1):
        arr[x] = temp[x]


# 示例用法
arr = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
sorted_arr = merge_sort(arr)
print("Sorted array:", sorted_arr)