题目描述

归并排序

算法1

(归并) $O(nlog(n))$

Python 代码

n = int(input())
seq = list(map(int, input().split()))

def merge_sort(q, l, r):
    if l >= r:
        return
    mid = (l + r) // 2
    merge_sort(q, l, mid)
    merge_sort(q, mid + 1, r)
    k, i, j = 0, l, mid + 1
    while i <= mid and j <= r:
        if q[i] < q[j]:
            tmp[k] = q[i]
            k += 1
            i += 1
        else:
            tmp[k] = q[j]
            k += 1
            j += 1
    while i <= mid:
        tmp[k] = q[i]
        k += 1
        i += 1
    while j <= r:
        tmp[k] = q[j]
        k += 1
        j += 1
    i, j = l, 0
    while i <= r:
        q[i] = tmp[j]
        j += 1
        i += 1

tmp = [0] * n
merge_sort(seq, 0, n-1)
for i in seq:
    print(i, end = " ")