实现归并排序（Mergesort）时代码挂起，请求排查问题

嘿，我帮你找出了程序卡住不终止的问题根源，主要有两个关键点需要修复：

1. Merge函数的死循环陷阱 #

你的merge函数漏掉了两个列表首元素相等的情况！当clist[0] == dlist[0]时，所有if/elif条件都不匹配，导致while True无限循环，程序永远跳不出这个循环返回结果。

看你原merge函数的核心逻辑：

def merge(clist, dlist):
    #assume inputs are sorted
    merged = []
    while True:
        if len(clist) == 0:
            return merged + dlist
        elif len(dlist) == 0:
            return merged + clist
        elif clist[0] < dlist[0]:
            merged.append(clist[0])
            del clist[0]
        elif clist[0] > dlist[0]:
            merged.append(dlist[0])
            del dlist[0]
    return merged

当两个首元素相等时，没有对应的分支处理，循环会一直原地打转。

修复方案 #

把最后一个elif改成else，直接处理大于或等于的情况；或者换一种更高效的索引遍历写法（避免del clist[0]这种O(n)的低效操作）：

def merge(clist, dlist):
    merged = []
    i = j = 0
    # 双指针遍历两个有序列表
    while i < len(clist) and j < len(dlist):
        if clist[i] <= dlist[j]:
            merged.append(clist[i])
            i += 1
        else:
            merged.append(dlist[j])
            j += 1
    # 拼接剩余未遍历的元素
    merged.extend(clist[i:])
    merged.extend(dlist[j:])
    return merged

2. Mergesort循环逻辑的优化 #

原代码里的while True循环虽然能运行，但逻辑不够直观，容易出现边界问题。可以把循环条件改成while len(alist) > 1，这样只要列表还没合并成一个，就继续循环，逻辑更清晰：

def mergesort(alist):
    alist = [[i] for i in alist]
    
    def merge(clist, dlist):
        merged = []
        i = j = 0
        while i < len(clist) and j < len(dlist):
            if clist[i] <= dlist[j]:
                merged.append(clist[i])
                i += 1
            else:
                merged.append(dlist[j])
                j += 1
        merged.extend(clist[i:])
        merged.extend(dlist[j:])
        return merged
    
    while len(alist) > 1:
        if len(alist) % 2 == 0:
            # 偶数长度，两两合并
            alist = [merge(alist[2*i], alist[2*i+1]) for i in range(len(alist)//2)]
        else:
            # 奇数长度，先取出最后一个元素，处理完偶数部分再放回
            last_element = alist.pop()
            alist = [merge(alist[2*i], alist[2*i+1]) for i in range(len(alist)//2)]
            alist.append(last_element)
    # 最终只剩一个排序好的列表，取出返回
    return alist[0]

现在测试你提供的输入：

print(mergesort([10, 5, 8, 16, 258, 11, 1, 20, 489, 10, 5, 3, 12]))

会得到正确的排序结果：[1, 3, 5, 5, 8, 10, 10, 11, 12, 16, 20, 258, 489]，而且程序会正常终止。

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