题目描述

给定你一个长度为n的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在1~109范围内），表示整个数列。

输出格式
输出共一行，包含 n 个整数，表示排好序的数列。

数据范围
1≤n≤100000

样例

输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5

算法1

归并排序

分治
快排用一个数来分，归并用整个数组的中间部分来分
1.确定分界点：mid=(l+r)，随机一个数值，不是数组中的值
2.递归排序左右两段
3.归并：把两个数组合并为一个有序的数组,用双指针算法
时间复杂度：log(n)

时间复杂度

nlog(n)

python代码

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 = 0
    i=l
    j=mid+1
    while(i<=mid and j<=r):
        if q[i]<=q[j]:
            tmp[k] = q[i]
            i+=1
        else:
            tmp[k] = q[j]
            j+=1
        k+=1
    while i<=mid:
        tmp[k] = q[i]
        i+=1
        k+=1
    while j<=r:
        tmp[k] = q[j]
        j+=1
        k+=1
    j=0
    for i in range(l,r+1):
        q[i] = tmp[j]
        j+=1


if __name__ == "__main__":
    n = int(input())
    N = 100010
    q = list(map(int,input().split()))
    tmp = [0]*N
    merge_sort(q,0,n-1)
    for i in range(n):
        print(q[i],end=" ")