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

代码中有 2 个错误：

if first < last: 应该是 if first < last and last-first >= 2:
merge_sort(A, middle+1, last) 应该是 merge_sort(A, middle, last)

Answer 2

问题出在这里：

    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 时，你首先得到中间 == 并陷入无休止的递归（被 RuntimeError: maximum recursion depth exceeded 停止）

所以要走的路是：

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

在那个小改动之后，您的实施给出了正确的结果。

python 合并排序问题

python merge sort issue

python

algorithm

sorting

mergesort

clrs