Merge sort in python не обновляет массив после сортировки

Question

ab = [5, 89, 23, 9] 

def mergsort(array):   
    mid = len(array)/2 
    if mid > 0: 
     print (array) 
     mergsort(array[:mid]) 
     mergsort(array[mid:]) 
     print(array) 
     merg(array) 
    return array 

def merg(array): 
    print (array) 
    mid = len(array)//2 
    left = array[:mid] 
    right = array[mid:] 
    i = j = k = 0 

    while i < len(left) and j < len(right): 
     if left[i] < right[j]: 
      array[k] = left[i] 
      i+=1 

     else: 
      array[k] = right[j] 
      j+=1 
     k+=1 

    while i < len(left):  
     array[k]=left[i] 
     i+=1 
     k+=1 

    while j < len(right):  
     array[k] = right[j] 
     j+=1 
     k+=1 
    print (array) 

mergsort(ab) 
print (ab) 

Функция слияния сортирует заданный массив и обновляется массив. Но в следующей рекурсии массив, входящий в функцию merg, не является мутированным массивом.

В примере, первая сортировка происходит, и [5,89] и [23,9] сортируются в [5,89] и [9,23], но объединенный входе в следующей рекурсии [5,89,23,9] вместо [5,89,9,23].

Я не могу найти причину, поскольку мутация массива должна влиять на родительский массив.

Answer 1

Одна проблемы с рекурсивными вызовами:

mergsort(array[:mid]) 
    mergsort(array[mid:]) 

результатов этих вызовов не регистрируются - поэтому, когда мы по-прежнему, это сделано с тем же самым оригинальным несортированным массивом.

Исправление:

def mergsort(array):  
    if len(array) == 1: 
     return array 
    mid=len(array)/2 
    left = mergsort(array[:mid]) # save into a parameter 
    right = mergsort(array[mid:]) # save into a parameter 
    return merge(left, right) # use the previous two 

Вторая проблема на самом деле такой же вопрос только:

def merg(array) 

операция слияния выполняется между двумя массивами, что означает, что две различные массивы должны быть отправлен на эту функцию, в противном случае нет никакого воспоминания о mid от функции mergesort() и объявление mid должно быть length/2 рассматривает весь массив, а не отдельные две части, которые мы int конец для слияния. Идея логики внутри этой функции правильная, но должна быть сделана, как я уже упоминал, на двух «отличных» массивах.

Последняя проблема является своп на месте, которое неправильно сделано, например, в:

array[k]=right[j] 

делая делать, мы стиранию элемент в array[k]!

Исправление:

def merge(left, right): 
    if len(left+right) < 2: 
     return left+right 
    res = [] 
    i = j = 0 
    while i < len(left) and j < len(right): 
     if left[i] < right[j]: 
      res.append(left[i]) 
      i += 1 
     elif j < len(right): 
      res.append(right[j]) 
      j += 1   
    while i < len(left): 
     res.append(left[i]) 
     i += 1 
    while j < len(right): 
     res.append(right[j]) 
     j += 1 
    return res 

После применения исправления как и работает:

print mergsort(ab) 

Выход:

[5, 9, 23, 89] 

по мере необходимости.