python перетасовывает мой список

Question

Я пытаюсь реализовать алгоритм сортировки слияния, используя списки в Python. Мой код слияния в порядке (я не стану его здесь прямо сейчас, но если вы спросите меня, я могу с радостью опубликовать его), но когда он вернется к рекурсивному уровню выше, список будет перетасован, и я не знаю Зачем.

Чтобы проиллюстрировать это, Что происходит:

array 1: [56] 
array 2: [96] 
merged array: [56, 96] # the merge is fine 

array 1: [76] 
array 2: [73] 
merged array: [73, 76] # here too 

Обратите внимание, что слияние действительно хорошо. Но, обратите внимание также, что «массив 2» в следующем разделе перемешивается (теоретически это тот же список, как [73, 76] выше)

array 1: [56, 96] 
array 2: [76, 73]   # this is broken 
merged array: [56, 76, 73, 96] 

Это происходит случайным образом с помощью рекурсивного выполнения. Обратите внимание, здесь, что это происходит в массив 1, а не массив 2, показывая, что ошибка не в моем коде:

array 1: [96] 
array 2: [34] 
merged array: [34, 96] 

array 1: [19] 
array 2: [34] 
merged array: [19, 34] 

array 1: [96, 34]   # this is broken too 
array 2: [19, 34] 
merged array: [19, 34, 96, 34] 

Таким образом, я никогда не могу заказать список, используя этот вид слияния. Если список python - упорядоченная последовательность, может кто-нибудь знать, почему это происходит?

Как спросил, вот код:

def merge_sort(array): 
    if len(array) > 1: 
     array1, array2 = partition(array) 
     merge_sort(array1) 
     merge_sort(array2) 
     array = merge(array1, array2) 
    return array 

def partition(array): 
    n = len(array)/2 
    array1 = array[0:n] 
    array2 = array[n::] 

    return array1, array2 

def merge(a, b): 
    array = [] 
    while len(a) > 0 or len(b) > 0: 
     if len(a) > 0 and len(b) > 0: 
      if a[0] <= b[0]: 
       array.append(a.pop(0)) 
      else: 
       array.append(b.pop(0)) 
     elif len(a) > 0: 
      array.append(a.pop(0)) 
     elif len(b) > 0: 
      array.append(b.pop(0)) 
    return array 

Answer 1

Слияние рода является разделяй-и-властвуй алгоритм: вы нарушаете проблемы в различных подзадач (делят часть), а затем объединить для решения проблемы (impera часть).

В сортировке слияний, divide Часть должна заказать два подсписок, созданных в вашем списке. impera часть принимает эти два заказывал подсписок и объединяет их в уникальном упорядоченном списке. При вызове:

merge([56, 96], [76, 73]) 

Это не может работать, потому что функция слияния ваша властвуй часть, которая ожидает подсписки заказываются. Ваш код не работает, потому что вы не сохраняете упорядоченные подсписки, но вы отбрасываете их, так как вы не сортируете массив на месте. Вместо того, чтобы:

merge_sort(array1) 

Вы должны иметь:

array1 = merge_sort(array1) 

В противном случае, когда вы звоните:

merge(array1, array2) 

подсписков не упорядочены.