algorithm - 有人可以向我解释每个循环和变量在自下而上合并排序中的含义吗？

Question

我很难理解自下而上合并排序算法的伪代码。

从概念上讲，我有点理解正在发生的事情。

1. 我们遍历数组并将每个元素分离到它自己的数组中
2. 我们合并前两个相邻数组(每个数组包含 1 个元素)以创建一个包含 2 个元素的新排序数组。
3. 我们再次遍历数组，这次将放入的元素数量加倍一个新数组。这些元素已经通过之前的合并和迭代步骤进行了排序。
4. 我们合并前两个相邻的数组(这次每个数组包含 2 个已排序元素)以创建一个包含 4 个元素的新排序数组。
5. 这个过程一直持续到整个数组排序完毕。

我正在查看来自该站点的伪代码 - http://www.algorithmist.com/index.php/Merge_sort

Input: array a[] indexed from 0 to n-1.

m = 1
while m < n do
    i = 0
    while i < n-m do
        merge subarrays a[i..i+m-1] and a[i+m .. min(i+2*m-1,n-1)] in-place.
        i = i + 2 * m
    m = m * 2

但是我在第一个 while 循环后迷路了!递归实现对我来说更直观，但迭代方法让我失望!如果有人能用 python 或 c++ 实现它，并解释每个步骤，以及每个变量的用途，我将不胜感激。

干杯!

Answer 1

m 是一起排序的元素数。它从 1 个元素开始，并不断加倍，直到我们将列表的一半与另一半合并。
n 是列表的大小。
i 是要合并的第一个子数组的第一个元素的索引。
i + m 是要合并的第二个子数组的第一个元素。

这是一个简单的例子。

Say I have the following n=5 list: a = [3,1,2,5,4]

m = 1:
    Merge each 1 element subarray with its 1 element neighbor subarray

    i = 0:
        Merge [3] and [1] -> [1,3]
        a is now [1,3,2,5,4]

    i = 2:
        Merge [2] and [5] -> [2,5]
        a is now [1,3,2,5,4]

m = 2:
    Merge each 2 element subarray with its 2 element neighbor subarray

    i = 0:
        Merge [1,3] and [2,5] -> [1,2,3,5]
        a is now [1,2,3,5,4]

m = 4:
    Merge each 4 element subarray with its 4 element neighbor subarray

    i = 0:
        Merge [1,2,3,5] and [4]
        a is now [1,2,3,4,5]. We're done sorting.