python - Merge sort problem, the code is wrong in the recursion procedure

Question

I am working on merge sort, which is written in a recursive procedure, but it is not right, I print every procedure

import math
def merge_sort(A):
    l=len(A)
    if l>1:
        merge_sort(A[:math.floor(l/2)])
        merge_sort(A[math.floor(l/2):])
        merge(A)
def merge(A):
    l=len(A)
    half1=A[:math.floor(l/2)]
    half2=A[math.floor(l/2):]
    l1=len(half1)
    l2=len(half2)
    B=[]
    for i in range(l):
        if l1 == 0:
            B.append(half2[len(half2)-l2])
            l2-=1
        elif l2 == 0:
            B.append(half1[len(half1)-l1])
            l1-=1
        elif half1[len(half1)-l1] <= half2[len(half2)-l2]:
            B.append(half1[len(half1)-l1])
            l1-=1
        elif half2[len(half2)-l2] < half1[len(half1)-l1]:
            B.append(half2[len(half2)-l2])
            l2-=1
    for i in range(l):
        A[i]=B[i]
    print(A)
A=[5,3,2,8,6,7,11,9,111,3]
merge_sort(A)

In order to find where is wrong, I print out every step, which gives me

[3, 5]
[6, 8]
[2, 8, 6]
[2, 5, 3, 8, 6]
[7, 11]
[3, 111]
[9, 111, 3]
[7, 9, 11, 111, 3]
[5, 3, 2, 7, 8, 6, 11, 9, 111, 3]

question from:https://stackoverflow.com/questions/65622882/merge-sort-problem-the-code-is-wrong-in-the-recursion-procedure

Answer 1

Slicing gives a new array, so your recursive merge_sort calls are not acting in-place (i.e. on the input array itself). As a result, nothing is being done on the input array.

To demonstrate, consider this snippet:

a = [1, 2, 3]
b = a[:]
b[0] = 0
assert a[0] == b[0] # raise AssertionError

Also, there are more things wrong: you need to return the new sorted sublists in merge_sort, then merge them together (taking in two lists instead of just having one parameter). I suggest going through the instruction line-by-line and try again.