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

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

Вы сортируете вторую часть только из середины + 1, когда вы должны начать с середины. На самом деле, вы никогда не переупорядочиваете элемент в середине.

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

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

потому что когда last = first + 1, вы получаете середину == first и погружаетесь в бесконечную рекурсию (останавливается 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)