合并排序 - 这个递归实现代码有效，但我有一个关于"In-Place"的问题

Question

1 def merge_sort(arr):
2    
3    if len(arr) > 1:
4        # Divide the array into two halves
5        mid = len(arr) // 2
6        left_half = arr[:mid]
7        right_half = arr[mid:]
8        
9        # Recursively sort the left and right halves
10        a = merge_sort(left_half)
11        b = merge_sort(right_half)
12        
13        print("left:", left_half, a)
14        print("right:", right_half, b)
15
16        # Merge the sorted halves
17        i = j = k = 0
18        while i < len(left_half) and j < len(right_half):
19            
20            if left_half[i] < right_half[j]:
21                arr[k] = left_half[i]
22                i += 1
23            else:
24                arr[k] = right_half[j]
25                j += 1
26            k += 1
27
28        # Check for any remaining elements in the left or right halves
29        while i < len(left_half):
30            arr[k] = left_half[i]
31            i += 1
32            k += 1
33
34        while j < len(right_half):
35            arr[k] = right_half[j]
36            j += 1
37            k += 1
38
39
40    return arr
41
42
43 res = merge_sort([2,3,1,5,6,4])
44 print(res)

上面代码的输出是:

left: [3] [3]
right: [1] [1]
left: [2] [2]
right: [1, 3] [1, 3]
left: [6] [6]
right: [4] [4]
left: [5] [5]
right: [4, 6] [4, 6]
left: [1, 2, 3] [1, 2, 3]
right: [4, 5, 6] [4, 5, 6]
[1, 2, 3, 4, 5, 6]

。.

我有一个关于这段代码的问题:

a = merge_sort(left_half)
b = merge_sort(right_half)

在我看来，没有上面的赋值(a和b)，代码隐式地这样做:

left_half = merge_sort(left_half)
right_half = merge_sort(right_half)

我不明白这个"in-place"修改是在这个递归过程中完成的?

Answer 1

这是因为在python中参数是通过引用传递的。
由于您直接在函数中修改arr，因此是否返回它并不重要。
如果你不想修改原始数组，我建议你在函数中创建一个arr的副本，然后修改并返回该副本。