[Python] 2751번 수 정렬하기2

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력

5
5
4
3
2
1

예제 출력

1
2
3
4
5

풀이

def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2
    low_lst = merge_sort(lst[:mid])
    high_lst = merge_sort(lst[mid:])

    merged_lst = []

    l = h = 0

    while l < len(low_lst) and h < len(high_lst):
        if low_lst[l] < high_lst[h]:
            merged_lst.append(low_lst[l])
            l += 1
        else:
            merged_lst.append(high_lst[h])
            h += 1

    merged_lst += low_lst[l:]
    merged_lst += high_lst[h:]
    return merged_lst


def solution(n):

    lst = []

    for _ in range(n):
        data = int(input())
        lst.append(data)

    lst = merge_sort(lst)

    for l in lst:
        print(l)


if __name__ == '__main__':
    n = int(input())

    solution(n)