Merge Sort Python Coding issues-CodePudding

def merge(array1: list, array2: list) -> list:
    result = []

    i = j = 0
    while i < len(array1) and j < len(array2):
        if array1[i] < array2[j]:
            result.append(array1[i])
            i  = 1
        else:
            result.append(array2[j])
            j  = 1

    # When we run out of elements in either L or M,
    # pick up the remaining elements and put in A[p..r]
    if i < len(array1):
        result  = array1[i:]
    if j < len(array2):
        result  = array2[j:]

    return result


def merge_sort(array: list) -> None:
    # if hi > lo
    if len(array) > 1:
        mid = (len(array)) // 2
        l = array[:mid]
        r = array[mid:]
        merge_sort(l)
        merge_sort(r)
        array[:] = merge(l, r)
        
        print(array)

My questions: First is about if I change array[:] = merge(l, r) -> array = merge(l,r) then the result will be messed up.

array = merge(l,r)

And another issue is why I cannot use code (below) directly. I have to refer to something.

merge_sort(array[:mid])
merge_sort(array[mid:])
array[:] = merge(array[:mid], array[mid:])

CodePudding user response：

For the first problem, assigning the merged results directly to the array will only make the it point to new list. Let's do a small experiment to observe this phenomenon:

>>> ar = list(range(10))
>>> same_ar = ar
>>> ar = []       # make `ar` point to a new list
>>> same_ar       # not change
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> ar = same_ar
>>> ar[:] = []    # modify `ar` in place
>>> same_ar       # change
[]

For the second problem, you should know that on the premise of solving the first problem, your merge_sort function is modifying the incoming list, but each time you use slicing, you will get a copy of the list, which causes the function to sort on the copy instead of the original list. Similarly, take a small experiment as an example:

>>> ar = list(range(10, -1, -1))
>>> ar
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
>>> half = ar[:5]     # a copy of first half of `ar`
>>> half
[10, 9, 8, 7, 6]
>>> half.sort()       # modify `half` in place
>>> half
[6, 7, 8, 9, 10]
>>> ar                # not change
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]