我在网上找到了以下代码：
def merge(left, right): result = [] i ,j = 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result += left[i:] result += right[j:] return result def mergesort(list): if len(list) < 2: return list middle = len(list) / 2 left = mergesort(list[:middle]) right = mergesort(list[middle:]) return merge(left, right)
当我运行它时，它可以100％工作。我只是不真正了解合并排序的工作方式或递归函数如何能够正确地左右对齐。
我相信理解合并排序的关键是理解以下原则-我将其称为合并原则：
给定两个单独的列表A和B，从最小到最大顺序排列，通过反复比较A的最小值和B的最小值，删除较小的值，并将其附加到C上，构造一个列表C。将其他列表中的其余项目按顺序移到C上。列表C也是排序列表。
如果您手工进行几次，您会发现它是正确的。例如：
A = 1, 3 B = 2, 4 C = min(min(A), min(B)) = 1 A = 3 B = 2, 4 C = 1 min(min(A), min(B)) = 2 A = 3 B = 4 C = 1, 2 min(min(A), min(B)) = 3 A = B = 4 C = 1, 2, 3
现在A已用尽，因此用B中的剩余值扩展C：
C = 1, 2, 3, 4
合并原理也很容易证明。A的最小值小于A的所有其他值，B的最小值小于B的所有其他值。如果A的最小值小于B的最小值，那么它也必须小于小于B的所有值。因此，它小于A的所有值和B的所有值。
因此，只要您继续将满足这些条件的值附加到C，您就会获得排序列表。这就是merge上面的功能。
merge
现在，有了这个原理，就很容易理解一种排序技术，它通过将列表分成较小的列表，对这些列表进行排序，然后将这些排序后的列表合并在一起来对列表进行排序。该merge_sort函数只是将列表分为两半，对这两个列表进行排序，然后按照上述方式将这两个列表合并在一起的函数。
merge_sort
唯一要注意的是，因为它是递归的，所以当对两个子列表进行排序时，它是通过将它们传递给自身来实现的！如果您在这里难以理解递归，建议先研究更简单的问题。但是，如果您已经掌握了递归的基础知识，那么您所要做的就是，已经对一个项目列表进行了排序。合并两个单项列表将生成一个已排序的两个项列表。合并两个两个项目列表会生成一个已排序的四个项目列表；等等。
