데이터를 분할하고 분할한 집합을 정렬하며 합친다.

(병합-> 투 포인터 이용 / 각 묶음의 앞을 가르키는 두 포인터에서 작은 값을 가져옴) -을 재귀 함수 형태

O(NlogN)

from sys import stdin
N = int(stdin.readline())
Nlist = [0]
for i in range(N):
    Nlist.append(int(stdin.readline()))
Mlist = [0]*(N+1) # 도움 리스트

def Mergesort(s, e): # 병합 정렬 / 오름차순
    if s == e: #가장 작은 덩어리부터 정렬시작
        return

    m = (s+e)//2
    Mergesort(s, m) # 두 덩어리로 나누기 / 재귀함수
    Mergesort(m+1, e)  

    for i in range(s, e+1): # 임시 리스트에 복사 / A가 정렬되는 리스트
        Mlist[i] = Nlist[i]

    #본정렬
    r = s # r은 정렬된 리스트의 인덱스
    point1 = s
    point2 = m+1
    while point1 <= m and point2 <= e: # 두 묶음 중 하나가 끝날때까지
        if Mlist[point1] < Mlist[point2]:
            Nlist[r] = Mlist[point1]
            point1 += 1
        else:
            Nlist[r] = Mlist[point2]
            point2 += 1
        r += 1

    while point1 <= m: # point1이 끝까지 못 갔다면
        Nlist[r] = Mlist[point1]
        point1 += 1
        r += 1
    while point2 <= e: # point2가 끝까지 못 갔다면
        Nlist[r] = Mlist[point2]
        point2 += 1
        r += 1

Mergesort(1,N)

for i in range(1,N+1):
    print(Nlist[i])