python merge sort issue

Question

Не знаю, где я ошибаюсь в моей реализации сортировки слияния в python.

import sys 

sequence = [6, 5, 4, 3, 2, 1] 

def merge_sort(A, first, last): 
    if first < last: 
     middle = (first + last)/2 
     merge_sort(A, first, middle) 
     merge_sort(A, middle+1, last) 
     merge(A, first, middle, last) 

def merge(A, first, middle, last): 
    L = A[first:middle] 
    R = A[middle:last] 

    L.append(sys.maxint) 
    R.append(sys.maxint) 

    i = 0 
    j = 0 
    for k in xrange(first, last): 
     if L[i] <= R[j]: 
      A[k] = L[i] 
      i = i + 1 
     else: 
      A[k] = R[j] 
      j = j + 1 

merge_sort(sequence, 0, len(sequence)) 
print sequence 

Я был бы очень признателен, если бы кто-нибудь мог указать, что нарушает мою текущую реализацию сортировки слияния.

Answer 1

Проблема здесь:

merge_sort(A, first, middle) 
    merge_sort(A, middle+1, last) # BEEP 

Вы только сортировать s econd part from middle + 1, когда вы должны начинать с середины. Фактически, вы никогда не переупорядочиваете элемент в середине.

Конечно, вы не можете писать либо

merge_sort(A, first, middle) 
    merge_sort(A, middle, last) # BEEP, BEEP 

, потому что, когда последний = первый + 1, вы получите среднюю == первый и погружение в бесконечной рекурсии (остановлен RuntimeError: maximum recursion depth exceeded)

Таким образом способ до:

merge_sort(A, first, middle) 
    if middle > first: merge_sort(A, middle, last) 

После этого небольшого изменения ваша реализация дает правильные результаты.

Answer 2

Есть 2 ошибки в коде:

• if first < last: должен быть if first < last and last-first >= 2:
• merge_sort(A, middle+1, last) должен быть merge_sort(A, middle, last)