求助：我的归并排序代码为何在特定列表下陷入无限循环？

你的归并排序代码在处理包含相等元素的列表时会陷入无限循环，问题出在merge函数的条件判断上：

问题原因 #

当A[i]和B[j]相等时，代码里的四个条件（i==m、j==n、A[i]<B[j]、A[i]>B[j]）都不满足，循环体没有任何操作，i和j的值保持不变，i+j永远无法达到m+n，导致while循环无限执行。

修复方案 #

只需要补充处理元素相等的情况，把最后一个elif改为else即可（相等时选择将任意一个列表的元素加入结果集并移动对应指针，不影响排序正确性）：

修复后的merge函数：

def merge(A,B): #merge A[0:m],B[0:n]
    (C,m,n)= ([],len(A),len(B))
    (i,j)=(0,0) # Current positions in A and B
    while i+j < m+n: # i+j is number of elements merged so far
        if i==m: # A is empty
            C.append(B[j])
            j += 1
        elif j==n: # B is empty
            C.append(A[i])
            i += 1
        elif A[i] < B[j]: # head of A is smaller than head of B
            C.append(A[i])
            i += 1
        else: # 处理A[i] >= B[j]的情况（包含相等）
            C.append(B[j])
            j += 1
    return C

修改后，所有情况都被覆盖，每次循环都会移动i或j，循环能正常结束，排序功能也能正确处理包含相等元素的列表。

内容的提问来源于stack exchange，提问作者F1_light