分而治之排序算法难度

Question

合并排序实现难以给出正确的输出：

def merge_sort(a):
    # array of 1 item or less returns the same array
    if len(a) <= 1:
        return a
    # index for middle of array
    m = math.floor(len(a) / 2)
    # Recursive method for dividing and sorting original array into smaller 
    # arrays
    a0 = merge_sort(a[0:m])
    a1 = merge_sort(a[m:])
    merge(a0, a1, a)
    return a

def merge(a0, a1, a):
    # Indices for arrays a1 and a0
    i0 = 0
    i1 = 0
    for i in range(len(a)):
        # Array no longer contains elements not already sorted into Array a
        if i0 == len(a0):
            a[i] = a1[i1]
            i1 += 1
        # Array no longer contains elements not already sorted into Array a
        elif i1 == len(a1):
            a[i] = a0[i0]
            i0 += 1
        # Comparing Arrays a1 and a0, then adding smaller element to 
        # original Array a
        elif a[i0] < a[i1]:
            a[i] = a0[i0]
            i0 += 1
        else:
            a[i] = a1[i1]
            i1 += 1

逻辑是正确的，但我的索引或引用可能有问题，只是我没有捕捉到。我的代码可能有什么问题，我该如何解决？

Answer 1

def merge(a0, a1, a):
    i0 = 0
    i1 = 0
    for i in range(len(a)):
        if i0 == len(a0):
            a[i] = a1[i1]
            i1 += 1
        elif i1 == len(a1):
            a[i] = a0[i0]
            i0 += 1
        elif a0[i0] < a1[i1]:
            a[i] = a0[i0]
            i0 += 1
        else:
            a[i] = a1[i1]
            i1 += 1

错误发生在merge()，你应该比较a0和a1而不是a。

Answer 2

第三个 elif 子句必须是

elif a0[i0] < a1[i1]:

分而治之排序算法难度

Divide and Conquer Sorting Algorithm Difficulty

python

mergesort