题解 | #成绩排序#

# 为了满足时间复杂度，选用稳定的归并排序，要返回排序后的原下标
# 其实排序时不需要稳定，只要输出时稳定就行，这有两个30分，你告诉我哪个是谁的，我说是谁的就是谁的！
def MergeSort(lst, mode=1):
    """
    lst: 待排序的列表
    mode: 排序模式, mode=0为降序, mode=1为升序
    """
    def merge(arr, ids, left, mid, right):
        nonlocal mode
        # 待合并的两段的指针
        i = left
        j = mid+1
        tmp = []
        itmp = []
        while i <= mid and j <= right: # 这个while保证先从两个已排好的段中去除小的部分
            if mode == 1:
                if arr[i] <= arr[j]: # 这里的=保证了稳定性
                    tmp.append(arr[i])
                    itmp.append(ids[i])
                    i += 1
                else:
                    tmp.append(arr[j])
                    itmp.append(ids[j])
                    j += 1
            else:
                if arr[i] >= arr[j]: # 这里的=保证了稳定性
                    tmp.append(arr[i])
                    itmp.append(ids[i])
                    i += 1
                else:
                    tmp.append(arr[j])
                    itmp.append(ids[j])
                    j += 1
        while i <= mid: # 以下两个while不用验证mode是因为段内已经排好顺序
            tmp.append(arr[i])
            itmp.append(ids[i])
            i += 1
        while j <= right:
            tmp.append(arr[j])
            itmp.append(ids[j])
            j += 1
        for i in range(left, right+1):
            arr[i] = tmp[i - left]
            ids[i] = itmp[i - left]
        
    def mSort(arr, ids, left, right):
        if left >= right:
            return
        mid = (left+right)// 2
        mSort(arr, ids, left, mid)
        mSort(arr, ids, mid+1, right)
        merge(arr, ids, left, mid, right)
    
    n = len(lst)
    ids = list(range(n)) # 原下标顺序列表
    if n <= 1:
        return lst
    mSort(lst, ids, 0, n-1)
    return lst, ids





while True:
    try:
        num = int(input().strip())
        mode = int(input().strip())
        na_list = list()
        sc_list = list()
        for _ in range(num):
            name, score = input().strip().split(' ')
            score = int(score)
            na_list.append(name)
            sc_list.append(score)
        sc_list, ids = MergeSort(sc_list, mode)
        for i, index in enumerate(ids):
            print(' '.join([na_list[index], str(sc_list[i])]))
    except:
        break

机试可不要这么写，太浪费时间了！！！

最后的空间复杂度没有满足要求，是O(2n)。应该还能优化，不过看了大佬题解我放弃这个思路了。同好们自己有时间去优化吧！