-1
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?

2
  • arr[k] = left_half[i] This code, and other lines like it, assign to arr. This is how arr is modified in-place. Commented Apr 11, 2023 at 16:31
  • @JohnGordon I do understand that, maybe let me edit my question to reflect my query in a clearer manner.
    – rustlecho
    Commented Apr 11, 2023 at 16:37

1 Answer 1

0

It is because in python arguments are passed by reference.
Since you are modifying arr directly in your function, it does not matter if you return it or not.
If you do not want to modify the original array, I suggest you to create a copy of arr inside your function and then modify and return that copy.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.