Python通用归并排序算法运行报错：类实例列表排序求助

我需要用归并排序对ClientInfo类的实例列表按name字段排序，已实现带key和reverse参数的通用mergesort函数，但运行时出现报错。补充说明：非通用版本的该函数可正常运行，但我需要通用版本。

我的实现代码：

def mergesort(lst, *, key=lambda x: x, reverse=False):
    """
    MergeSort implementation
    :param lst: the list that will be sorted
    :param key: the function by witch it is sorted
    :param reverse: True - ascending sort, False - descending sort
    :return: return the sorted list
    """
    if len(lst) > 1:
        pivot = len(lst) // 2
        left_half = lst[:pivot]
        right_half = lst[pivot:]

        mergesort(left_half)
        mergesort(right_half)

        i = 0
        j = 0
        k = 0
        while i < len(left_half) and j < len(right_half):
            if reverse is False:  # ascending sort
                if key(left_half[i]) < key(right_half[j]):
                    lst[k] = left_half[i]
                    i += 1
                else:
                    lst[k] = right_half[j]
                    j += 1
                k += 1
            elif reverse is True:  # descending sort
                if key(left_half[i]) < key(right_half[j]):
                    lst[k] = right_half[j]
                    j += 1
                else:
                    lst[k] = left_half[i]
                    i += 1
                k += 1

问题分析与修复 #

你的代码存在三个核心问题：

• 递归调用未接收排序后的子列表：切片生成的left_half和right_half是新列表，递归排序后需要将结果重新赋值给这两个变量，否则后续merge操作使用的还是未排序的原切片。
• 未处理merge阶段的剩余元素：当其中一个子列表遍历完后，另一个子列表的剩余元素需要全部复制到结果列表中。
• 函数未返回排序后的列表，且reverse参数的注释与逻辑完全相反。

修复后的代码：

def mergesort(lst, *, key=lambda x: x, reverse=False):
    """
    MergeSort implementation
    :param lst: the list that will be sorted
    :param key: the function by which it is sorted
    :param reverse: False - ascending sort, True - descending sort
    :return: return the sorted list
    """
    if len(lst) > 1:
        pivot = len(lst) // 2
        left_half = lst[:pivot]
        right_half = lst[pivot:]

        # 递归排序子列表并接收结果
        left_half = mergesort(left_half, key=key, reverse=reverse)
        right_half = mergesort(right_half, key=key, reverse=reverse)

        i = j = k = 0
        # 合并两个已排序的子列表
        while i < len(left_half) and j < len(right_half):
            if not reverse:  # 升序排序
                if key(left_half[i]) < key(right_half[j]):
                    lst[k] = left_half[i]
                    i += 1
                else:
                    lst[k] = right_half[j]
                    j += 1
            else:  # 降序排序
                if key(left_half[i]) > key(right_half[j]):
                    lst[k] = left_half[i]
                    i += 1
                else:
                    lst[k] = right_half[j]
                    j += 1
            k += 1
        
        # 处理左半部分剩余元素
        while i < len(left_half):
            lst[k] = left_half[i]
            i += 1
            k += 1
        
        # 处理右半部分剩余元素
        while j < len(right_half):
            lst[k] = right_half[j]
            j += 1
            k += 1
    # 返回排序后的列表
    return lst

关键修改点 #

• 递归调用时传递key和reverse参数，并将排序后的子列表重新赋值给left_half和right_half。
• 新增两个while循环，处理merge阶段未遍历完的剩余元素。
• 修正reverse参数的注释，同时优化降序排序的判断逻辑（直接用>更直观）。
• 补充函数末尾的return lst语句，确保返回排序后的结果。

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