[알고리즘] 정렬 - 병합 정렬

❗병합 정렬

• 병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer)기법과 재귀 알고리즘을 이용한 정렬 알고리즘으로 시간 복잡도는 O(N log N)이다. 하나의 리스트를 두 개의 균등한 크기로 분할하고 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는 방법이다. 병합 정렬은 분할(Divide)과 정복(Conquer)이라는 것에 기초하여 정렬이 수행된다.

• 분할(Divide) : 입력 리스트를 같은 크기의 2개 부분 리스트로 분할한다.
  ★부분 리스트의 크기가 1이 될 때까지 계속 분할한다.
• 정복(Conquer) : 부분 리스트를 정렬한다.
• 결합(Combine) : 정렬된 부분 리스트를 하나의 리스트로 통합한다.

1) 정렬되지 않은 데이터

2) 부분 리스트의 길이가 1이 될 때까지 분할

3) 길이가 1인 쪼개진 리스트들은 길이가 1개이므로 정렬이 수행된 것과 같다고 볼 수 있으므로 이들을 병합하여 리스트들을 통합해나가면서 정렬 리스트에 저장

import sys
input = sys.stdin.readline

def MergeSort(lt, rt):
	# 왼쪽 포인터가 오른쪽 포인터가 작은 경우
    if lt < rt:
    	# 중간 지점을 구하기
        mid = (lt + rt) // 2
        # 왼쪽 리스트 병합 정렬
        MergeSort(lt, mid)
        # 오른쪽 리스트 병합 정렬
        MergeSort(mid+1, rt)
        p1 = lt
        p2 = mid+1
        tmp = []
        while p1 <= mid and p2 <= rt:
            if arr[p1] < arr[p2]:
                tmp.append(arr[p1])
                p1 += 1
            else:
                tmp.append(arr[p2])
                p2 += 1
        # 나머지 들어가지 못한 원소들 마저 추가
        if p1 <= mid:
            for i in range(p1, mid+1):
                tmp.append(arr[i])
        if p2 <= rt:
            for i in range(p2, rt+1):
                tmp.append(arr[i])
        # 복사된 배열 tmp를 arr에 넣는다.
        for i in range(len(tmp)):
            arr[lt+i] = tmp[i]

arr = [23, 11, 45, 36, 15, 67, 33, 21]
print("Before Sort: ", end=" ")
print(arr)
MergeSort(0, len(arr)-1)
print("After Sort: ", end=" ")
print(arr)