algorithm - 我知道合并排序是如何工作的，但合并排序代码是如何工作的？

Question

您可以在维基百科上阅读此内容:

function merge_sort(list m)
// Base case. A list of zero or one elements is sorted, by definition.
if length(m) <= 1
    return m

// Recursive case. First, *divide* the list into equal-sized sublists.
var list left, right
var integer middle = length(m) / 2
for each x in m before middle
     add x to left
for each x in m after or equal middle
     add x to right

// Recursively sort both sublists
left = merge_sort(left)
right = merge_sort(right)

// Then merge the now-sorted sublists.
return merge(left, right)

第 1 行有一个数字列表，比方说 9 6 3 7 5 1 8 2

他们说 merge_sort 在 2 和 2 上一次又一次地划分列表，直到每个列表只剩下 1 个整数，就像这个:

9 6 3 7 5 1 8 2 -->
9 6 3 7 - 5 1 8 2 -->
9 6 - 3 7 - 5 1 - 8 2 -->
9 - 6 - 3 - 7 - 5 - 1 - 8 - 2

然后数字像这样放在一起:

6 9 - 3 7 - 1 5 - 2 8 -->
3 6 7 9 - 1 2 5 8 -->
1 2 3 5 6 7 8 9 -->

但我没看到代码中的整数列表在哪里一次又一次地除以 2，直到每个只剩下 1 个整数？

var list left, right
var integer middle = length(m) / 2
for each x in m before middle
     add x to left
for each x in m after or equal middle
     add x to right

据我了解，在上面的代码中，数字列表分为两个不同的列表:9 6 3 7 和 5 1 8 2

下面的代码会发生什么？

left = merge_sort(left)
right = merge_sort(right)

谁能给我解释一下上面的 merge_sort 代码是如何一步步工作的？

Answer 1

But I don't see where in the code the list of integers are divided on 2 again and again until each has only 1 integer left?

var list left, right
var integer middle = length(m) / 2          --------statement-1
for each x in m before middle               --------statement-2
   add x to left
for each x in m after or equal middle       --------statement-3
   add x to right

在 statement-1 中，您将数组分成两部分并将它们添加到 left 和 right 子数组中。在 statement-2 中，您添加了 middle 之前的所有元素，这是数组的中间元素。类似地，statement-3，您要在右子数组中添加其余元素。所以本质上，您继续将数组分成两部分，直到它们的大小为 1 或 0。

if length(m) <= 1
    return m

一开始你有上面的条件检查，如果数组的大小小于或等于一，它返回方法调用。

What then happens on the code below?

left = merge_sort(left)
right = merge_sort(right)

这是对每个子数组进行排序(划分数组直到大小为一)的递归调用。这是在上面的伪代码中创建的。您分别对 left 和 right 子数组进行排序，然后将它们连接到一个数组中。

return merge(left, right)

此处 left 和 right 子数组都传递给 merge 函数。这两个数组都是排序数组。 merge 函数的任务是将这些子数组合并为一个排序数组。