python hợp nhất vấn đề sắp xếp

Question

Không chắc chắn nơi tôi đang đi sai với việc thực hiện của tôi sắp xếp hợp nhất trong 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 

Tôi thực sự đánh giá cao nếu ai đó có thể chỉ ra điều gì đang phá vỡ việc triển khai sắp xếp hợp nhất hiện tại của tôi.

Answer 1

Vấn đề là ở đây:

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

Bạn chỉ loại các s econd phần từ giữa + 1, khi bạn nên bắt đầu ở giữa. Trong thực tế, bạn không bao giờ sắp xếp lại phần tử ở giữa.

Tất nhiên bạn không thể viết một trong hai

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

vì khi cuối cùng = đầu tiên + 1, bạn sẽ có được giữa == đầu tiên và lặn trong một đệ quy vô tận (chặn lại bởi một RuntimeError: maximum recursion depth exceeded)

Vì vậy, đường đi để đi là:

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

Sau ít thay đổi đó, việc triển khai của bạn sẽ cho kết quả chính xác.

Answer 2

Có 2 lỗi trong mã:

• if first < last: nên if first < last and last-first >= 2:
• merge_sort(A, middle+1, last) nên merge_sort(A, middle, last)