데이터를 분할하고 분할한 집합을 정렬하며 합친다.
(병합-> 투 포인터 이용 / 각 묶음의 앞을 가르키는 두 포인터에서 작은 값을 가져옴) -을 재귀 함수 형태
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])