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)
And the output for the above code is:
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]
. .
I have a question specifically regarding this chunk of code:
a = merge_sort(left_half)
b = merge_sort(right_half)
It seems to me that without the above assignment (a and b), the code is implicitly doing this:
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
I do not understand how this "in-place" modification is done during this recursion process?
arr[k] = left_half[i]
This code, and other lines like it, assign toarr
. This is howarr
is modified in-place.