Python数据结构题编写一个实验程序,采用自底而上的二路归并排序完成一个整数序列的递增排序,要求输出第一次排序的结果,并用相关数据进行测试

为了演示如何编写一个使用自底向上的二路归并排序算法对整数序列进行递增排序，并输出第一次排序结果，我们可以创建一个简单的Python函数。以下是代码实现的一个例子：

def merge_sort(arr):
    # 如果数组长度小于等于1，直接返回
    if len(arr) <= 1:
        return arr

    # 找到中间点
    mid = len(arr) // 2

    # 分割数组
    left_half = arr[:mid]
    right_half = arr[mid:]

    # 自底向上合并
    sorted_left = merge_sort(left_half)
    sorted_right = merge_sort(right_half)

    # 合并两个已排序的部分
    merged = []
    i = j = 0
    while i < len(sorted_left) and j < len(sorted_right):
        if sorted_left[i] <= sorted_right[j]:
            merged.append(sorted_left[i])
            i += 1
        else:
            merged.append(sorted_right[j])
            j += 1

    # 添加剩余元素（如果有的话）
    merged.extend(sorted_left[i:])
    merged.extend(sorted_right[j:])

    return merged


# 测试用例
test_arr = [5, 2, 9, 1, 7, 4, 6, 8, 3]
first_sorted_result = merge_sort(test_arr)

print("原始数组：", test_arr)
print("第一轮排序后的数组：", first_sorted_result)

#