如何修改归并排序算法以实现Python中元组列表的排序？

问题场景 #

原归并排序函数可正常处理整数列表，但修改为按元组索引1的值升序排序后，应用于元组列表：

tuplelist = [(1, 600), (2, 800), (3, 200)]

出现以下错误：

TypeError: 'int' object is not subscriptable.

原函数代码如下：

def mergeSort(arr):
    if len(arr) > 1:
 
        mid = len(arr)//2
 
        L = arr[:mid]
 
        R = arr[mid:]
 
        mergeSort(L)
 
        mergeSort(R)
 
        i = j = k = 0
 
        while i < len(L) and j < len(R):
            if L[i][1] <= R[j][1]:
                arr[k] = L[i][1]
                i += 1
            else:
                arr[k] = R[j][1]
                j += 1
            k += 1
 
        while i < len(L):
            arr[k] = L[i][1]
            i += 1
            k += 1
 
        while j < len(R):
            arr[k] = R[j][1]
            j += 1
            k += 1
    print(arr)

错误原因 #

你在合并阶段错误地将元组的第二个整数元素（比如L[i][1]）赋值给了arr[k]，而非保留整个元组。这会导致递归处理后续子数组时，数组内的元素变成了整数，再执行L[i][1]这类下标访问操作时，就会触发“整数不可下标访问”的错误。

修改方案 #

要实现按元组索引1的值升序排序，只需在合并时将整个元组存入结果数组即可，比较逻辑保持按[1]判断不变：

def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]

        mergeSort(L)
        mergeSort(R)

        i = j = k = 0

        # 按元组索引1的值比较，存入整个元组
        while i < len(L) and j < len(R):
            if L[i][1] <= R[j][1]:
                arr[k] = L[i]  # 改为存入完整元组
                i += 1
            else:
                arr[k] = R[j]  # 改为存入完整元组
                j += 1
            k += 1

        # 剩余元素同样存入完整元组
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
    print(arr)

# 测试
tuplelist = [(1, 600), (2, 800), (3, 200)]
mergeSort(tuplelist)
# 输出：[(3, 200), (1, 600), (2, 800)]

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