I'm writing a merge sort with recursion, but it doesn't print out the correct message, however when I'm hand writing through the code, it seems right. could anyone help me to find out why?

def mergeSort1(arr):
  
  if len(arr)<=1:  #base case
    return arr
  else :
    breakN =len(arr)//2
    left = arr[:breakN]
    right = arr[breakN:]
    mergeSort1(left)
    mergeSort1(right)
    i=j=0
    temp = []
    while i<len(left) and j<len(right):
      if left[i] <= right[j]:
        temp.append(left[i])
        i  = 1
      else:
        temp.append(right[j])
        j  = 1
    while i < len(left): # extend the list in case there's any missing
      temp.append(left[i])
      i  = 1
    while j < len(right):
      temp.append(right[j])
      j  = 1
    #print(temp)
    return temp

code to get the result:

arr = [9,7,3,6,2]
mergeSort1(arr)
print(arr)

and the result:

[9, 7, 3, 6, 2]

I then looked up at the code from other people, I found the problem might lie in temp[], so I added a print(temp) at the back of else statement(see above code), and it prints out the following:

[7, 9]
[2, 6]
[3, 6, 2]
[3, 6, 2, 9, 7]

It shows the first and second answer is what I want, could anyone please help me find out why ?

CodePudding user response：

Since you are not modifying the input list arr in-place and are returning a new list temp instead, you should assign the returning value of the function to a variable.

Change:

mergeSort1(left)
mergeSort1(right)

to:

left = mergeSort1(left)
right = mergeSort1(right)

And change:

mergeSort1(arr)
print(arr)

to:

print(mergeSort1(arr))

Alternatively, you can modify the input list in-place, in which case you can assign temp back to arr in-place using slice assignment.

Change:

return temp

to:

arr[:] = temp