MergeSort.py

# 04-5 병합 정렬
# - 분할 정복 divide and conquer 방식을 사용
# - 데이터를 분할하고 분할한 집합을 정렬하여 합치는 알고리즘
# - 시간 복잡도 O(n log n)

# 원리) [2, 4, 3, 6]을 병합 정렬로 정렬하는 과정을 보자
# step1. 각 요소를 부분집합으로 설정
# set1 = [2] set2 = [4] set3 = [3] set4 = [6]

# step2. 부분집합을 정렬하면서 합치기(병합하기), 여기선 오름차순으로 정렬하자.
# set1 = [2, 4] set2 = [3, 6]

# step3. step2를 다시 반복
# totalSet = [2,3,4,6]


# - 보통 투 포인터를 이용하여 왼쪽, 오른쪽 부분 집합을 병합한다.
# 왼쪽 포인터, 오른쪽 포인터의 값을 비교해서 더 작은 값을 결과 배열에 추가하고, 포인터를 오른쪽으로 1칸 이동시킨다.
# 이는 다양한 문제에서 응용하므로 반드시 숙지하자!

# Ex. List = [24, 32, 42, 60, 5, 15, 45, 90], resList = []
# step1. 두 부분 집합을 구분하자.
# set1 = [24, 32, 42, 60] set2 = [5, 15, 45, 90]

# step2. set1Inx가 가리키는 값과 set2Inx가 가리키는 값을 비교하자.

# 1) List[set1Inx] = 24, List[set2Inx] = 5
# => resList.append(List[set2Inx])

# 2) List[set1Inx] = 32, List[set2Inx] = 15
# => resList.append(List[set2Inx])

# 이 과정을 반복하면...
# resList = [5, 15, 24, 32, 42, 45, 60, 90]