Problem in understanding the concept of how values are stored and passed in Merge sort in Python

user_10681575 0
Viewed 45
def merge_sort(arr):
    if len(arr) <= 1:
        return

    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    print("Before " + str(left_half), str(right_half))

    merge_sort(left_half)
    merge_sort(right_half)

    print("After " + str(left_half), str(right_half))

    i = 0
    j = 0
    k = 0

    while i < len(left_half) and j < len(right_half):
        if left_half[i] <= right_half[j]:
            arr[k] = left_half[i]
            i += 1
        else:
            arr[k] = right_half[j]
            j += 1
        k += 1

    while i < len(left_half):
        arr[k] = left_half[i]
        i += 1
        k += 1

    while j < len(right_half):
        arr[k] = right_half[j]
        j += 1
        k += 1

if __name__ == "__main__":
li = list(map(int, input().split()))
merge_sort(li)
print(li)

Input: 3 34 1 2 1 3 2

Output:

Before [3, 34, 1] [2, 1, 3, 2]
Before [3] [34, 1]
Before [34] [1]
After [34] [1]
After [3] [1, 34]
Before [2, 1] [3, 2]
Before [2] [1]
After [2] [1]
Before [3] [2]
After [3] [2]
After [1, 2] [2, 3]
After [1, 3, 34] [1, 2, 2, 3]
[1, 1, 2, 2, 3, 3, 34]

I have a basic knowledge of how python works and also this code is working fine, but I don't understand that if we are not returning anything to update the value of the left_half or the right_half, how are they changing and storing the sorted values? As the sorted values are stored in arr and we didn't return those values anywhere.

Please help! Thank you.

mergesort pass-by-reference sorting python
1 Answers

left_half and right_half are temporary arrays defined with:

left_half = arr[:mid]    // left_half is a copy of the left half of arr
right_half = arr[mid:]   // right_half is a copy of the right half of arr

They are sorted in place with recursive calls to merge_sort:

merge_sort(left_half)
merge_sort(right_half)

The values from the sorted halves are then merged back into arr, which is updated in place and these temporary arrays are discarded upon returning from merge_sort.

merge_sort is a recursive function: there is a distinct set of temporary arrays created for each call.

user_45932670
Related