如何修改Merge Sort代码以输出排序过程中的所有移动操作

你当前的代码存在两个明显错误，导致只能重复打印最终结果：

• 外层写了for循环重复调用mergeSortn次：归并排序是递归分治实现，单次调用即可完成全数组排序，第一次调用结束后nums就已经是有序状态，后续调用不会产生任何修改，所以打印结果全相同
• 没有在归并逻辑中插入过程打印语句，自然看不到每一步的元素移动、合并操作

def mergeSort(nums, depth=0):
    if len(nums) > 1:
        mid = len(nums) // 2
        left = nums[:mid]
        right = nums[mid:]

        # 递归排序左右子片段
        mergeSort(left, depth+1)
        mergeSort(right, depth+1)

        i = j = k = 0
        # 打印当前层级待合并的两个子片段，缩进对应递归深度方便阅读
        print(f"{'  '*depth}待合并：左片段{left} | 右片段{right}")
        
        # 合并左右子片段
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                nums[k] = left[i]
                i += 1
            else:
                nums[k] = right[j]
                j += 1
            k += 1
        while i < len(left):
            nums[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            nums[k] = right[j]
            j += 1
            k += 1
        
        # 打印合并后的结果
        print(f"{'  '*depth}合并后：{nums}")

nums = [9, 7, 5, 3, 1]
print("初始数组：", nums)
mergeSort(nums)
print("最终排序结果：", nums)

运行上述代码会得到带层级的过程打印，你可以直观看到每一步合并操作：

初始数组： [9, 7, 5, 3, 1]
  待合并：左片段[9] | 右片段[7]
  合并后：[7, 9]
    待合并：左片段[3] | 右片段[1]
    合并后：[1, 3]
  待合并：左片段[5] | 右片段[1, 3]
  合并后：[1, 3, 5]
待合并：左片段[7, 9] | 右片段[1, 3, 5]
合并后：[1, 3, 5, 7, 9]
最终排序结果： [1, 3, 5, 7, 9]

如果你需要打印全局数组的实时变化、或者单个元素的移动记录，可以再修改打印逻辑，补充全局数组的索引参数，定位每一步修改的位置即可。

内容的提问来源于stack exchange，提问作者Spooderman