Python：就地合并排序实现问题

Question

我正在 python3 中实现就地合并排序算法。如果输入数组的长度大于一，则代码采用一个输入数组并递归地调用它（使用拆分数组作为输入）。之后，它连接两个排序数组。这是代码

def merge_sort(array):

    """
    Input : list of values
    Note :
        It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.
    Returns : sorted list of values

    """

    def join_sorted_arrays(array1, array2):

        """
        Input : 2 sorted arrays.
        Returns : New sorted array

        """

        new_array = []    # this array will contain values from both input arrays.
        j = 0             # Index to keep track where we have reached in second array
        n2 = len(array2)

        for i, element in enumerate(array1):
            # We will compare current element in array1 to current element in array2, if element in array2 is smaller, append it
            # to new array and look at next element in array2. Keep doing this until either array2 is exhausted or an element of
            # array2 greater than current element of array1 is found.
            while j < n2 and element > array2[j]:
                new_array.append(array2[j])
                j += 1
            new_array.append(element)
        # If there are any remaining values in array2, that are bigger than last element in array1, then append those to 
        # new array.
        for i in range(j,n2):
            new_array.append(array2[i])
        return new_array

    n = len(array)
    if n == 1:
        return array
    else:
        # print('array1 = {0}, array2 = {1}'.format(array[:int(n/2)], array[int(n/2):]))
        array[:int(n/2)] = merge_sort(array[:int(n/2)])
        array[int(n/2):] = merge_sort(array[int(n/2):])
        # print('array before joining : ',array)
        array = join_sorted_arrays(array[:int(n/2)],array[int(n/2):])
        # print('array after joining : ',array)
        return array

现在如果测试代码，

 a = [2,1,4,3,1,2,3,4,2,7,8,10,3,4]
 merge_sort(a)
 print(a)
 out : [1, 1, 2, 2, 3, 3, 4, 2, 3, 4, 4, 7, 8, 10]

如果您取消注释上述函数中的 print 语句，您会注意到，a = 给定输出，就在最后一次调用 join_sorted_arrays 之前。调用此函数后，应对数组 'a' 进行排序。令我惊讶的是，如果我执行以下操作，输出是正确的。

a = [2,1,4,3,1,2,3,4,2,7,8,10,3,4]
a = merge_sort(a)
print(a)
out : [1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 7, 8, 10]

我需要一些帮助来理解为什么会这样。我是初学者，所以也欢迎任何其他关于编码实践等的评论。

Answer 1

当您使用

将 array 重新分配为 join_sorted_arrays() 的输出时

array = join_sorted_arrays(array[:int(n/2)],array[int(n/2):])

您不再更新 a 的值。

当您将 a 作为参数 array 传入时，可以理解为什么函数中所有名为 array 的变量看起来都应该更新 [= 的原始值12=]（又名 a）。但是，array = join_sorted_arrays(...) 发生的情况是您在 merge_sort() 函数内有一个新变量 array。从函数 returns 返回 array 新的、排序的值集。

对 a 的引用在最后一条语句之前一直在修改，这就是为什么它看起来与 merge_sort(a 之后的 print(a) 不同的原因。但是您只能从 merge_sort() 的返回值中获得最终的排序输出。

如果你看一下可能会更清楚：

b = merge_sort(a)
print(a) # [1, 1, 2, 2, 3, 3, 4, 2, 3, 4, 4, 7, 8, 10]
print(b) # [1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 7, 8, 10]

请注意，Python 不是一种传递引用的语言，它实际上是什么的细节一开始可能有点奇怪。当我被绊倒时，我总是回去阅读它是如何工作的。有很多关于该主题的 SO 帖子，在这里可能对您有用。
例如，this one and this one.

Python：就地合并排序实现问题

Python: Inplace Merge sort implementation issue

python

mergesort