python - 为什么在 Python 中使用 Mergesort 时返回值为 0？

Question

我正在编写合并排序代码，但它没有排序。你知道它有什么问题吗？

def mergeSort(L):
   if len(L) == 1:
       return L
   else:
       # divide
       L1 = mergeSort(L[0:round(len(L)/2)])
       L2 = mergeSort(L[round(len(L)/2):len(L)])
    
       # merge
       i = 0
       j = 0
       K = []
       while i < len(L1) and j < len(L2):
           if L1[i] < L2[j]:
               K.append(L1[i])
               i=i+1
           else:
               K.append(L2[j])
               j=j+1
       return K

输入:

L = [1,2,5,7,8,0,10,21,32,53,16,16,48,59,64,53,75,52,42,21,98,76‌​] 

输出:

L = [0]

Answer 1

while i < len(L1) and j < len(L2):

我觉得这不对。在这种情况下，一旦 i 或 j 到达各自列表的末尾，循环就会结束。因此，另一个列表中可能仍有元素永远不会被迭代。

尝试将 and 更改为 or，并添加一些检查以确保列表间比较仅在两个列表都尚未完全迭代时才会发生:

    while i < len(L1) or j < len(L2):
        if i < len(L1) and (j == len(L2) or L1[i] < L2[j]):
            K.append(L1[i])
            i=i+1
        else:
            K.append(L2[j])
            j=j+1

现在你的代码输出 [0, 1, 2, 5, 7, 8, 10, 16, 16, 21, 21, 32, 42, 48, 52, 53, 53, 59, 64, 75 , 76, 98]。