[CS] 병합 정렬(Merge Sort)

컴퓨터의 창시자 폰 노이만이 개발한 정렬 알고리즘.
퀵 정렬과 함께 O(n log n)의 시간복잡도를 가지는 빠른 알고리즘 중의 하나이다.
퀵 정렬과 마찬가지로 분할 정복을 이용하는 알고리즘으로
최악의 경우 n^2의 시간복잡도를 가지는 퀵 정렬과 달리,
병합 정렬은 모든 경우에 n log n의 시간복잡도를 보장한다.

대략적인 절차를 설명하면 다음과 같다.
1.들어온 배열을 우선 반으로 쪼갠다.(홀수인 경우 반올림 또는 반내림한다)
2.나뉘어진 부분 각각을 다시 크기가 1이 될 때까지 재귀적으로 쪼갠다.
3.요소가 하나가 되면, 나뉘어진 부분끼리 비교하여,합치는 동시에 정렬을 진행한다.
4.위 과정을 재귀적으로 되돌아가 나뉘어진 부분을 각각 다시 정렬하며 합친다.
5.전부 합쳐지면 최종적으로 정렬된 배열이 나오게 된다.

위 알고리즘은 일반적으로 mergesort와 merge로 나누어진다.
다음은 파이썬으로 구현한 병합 정렬이다.

import time
import math

def mergesort(entries):
if isinstance(entries,list) and len(entries) > 1 :
pivot = math.floor(len(entries)/2)-1
first = mergesort(entries[:pivot+1])
second = mergesort(entries[pivot+1:])
return merge(first,second)
else:
return entries

def merge(first,second):
unit=[]

if not isinstance(first,list):
first = [first]
if not isinstance(second,list):
second = [second]

first_p = second_p = 0

while first_p <len(first) and second_p <len(second):
if first[first_p]<second[second_p]:
unit.extend([first[first_p]])
first_p+=1
else:
unit.extend([second[second_p]])
second_p+=1

if first_p>=len(first) and second_p<len(second):
unit.extend(second[second_p:])
else:
unit.extend(first[first_p:])

return unit



num = int(input())
entries = []
for i in range(0,num):
entries.extend([int(input())])

entries = mergesort(entries)
for n in entries:
print(str(n))