Python 代码

def mergesort(q, l, r):
    # 功能：使q[l: r+1]从小到大有序排列
    # 退出递归条件：
    if l >= r:
        return
    # 1. 确定分界点：
    mid = (l + r) // 2
    # 2. 递归排序
    mergesort(q, l, mid)
    mergesort(q, mid + 1, r)
    # 3. 归并，也就是将有序的q[l: mid+1]和q[mid+1: r+1]合并为新的有序数组
    # 使用双指针算法
    i, j = l, mid + 1
    res = []
    while i <= mid and j <= r:
        if q[i] <= q[j]: # 将q[i]先append到res中
            res.append(q[i])
            i += 1
        else: # 将q[j]先append到res中
            res.append(q[j])
            j += 1

    # 执行完上面的循环以后，q[j: r + 1]和q[i: mid + 1]一定有一个为空，而另一个不为空，因此以下两个语句每次实际上只有一个有意义
    # 左半部分为空则直接将右半部分拼接到res末尾
    res += q[j: r + 1]
    # 右半部分为空则直接将左半部分拼接到res末尾
    res += q[i: mid + 1]

    # 最后将合并后的有序数组还原到q的对应区间中
    q[l: r + 1] = res

if __name__ == "__main__":
    n = int(input())
    q = list(map(int, input().split()))
    mergesort(q, 0, n - 1)
    for e in q:
        print(e, end=" ")