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_数组之前。调用此函数后，应对数组“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的变量似乎都应该更新array（又称a）的原始值。但是相反，array=join_sorted_array（…）发生了什么是指在merge_sort（）函数中有一个新变量array作用域。从函数返回array将返回新的、已排序的值集。

直到最后一条语句，对a的引用一直在修改，这就是为什么在merge\u 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不是一种通过引用传递的语言，它实际上是什么的细节一开始对suss来说可能有点奇怪。当我被绊倒时，我总是回去读它是如何工作的。有很多关于这个话题的SO帖子，在这里可能对你有所帮助<例如，这个和这个。