Sorting algorithm(정렬 알고리즘) 3탄 - Merge Sort(합병 정렬)

3. Merge Sort (합병 정렬)

▪ 정렬된 두 리스트가 있을 때 (리스트1, 리스트2), 각각의 첫번째 수를 비교해서 작은 수를 정렬.

→ (리스트1의 첫번째 수가 정렬됐다고 가정하면,)

     리스트1의 두번째 수와 남은 수 즉, 리스트2의 첫번째 수를 비교해서 정렬.

→ 동일한 방식으로 계속 진행해서 정렬된 하나의 리스트를 만듦. (그래서 병합이라고 하나 봄!!!ㅋㅋㅋ)

 

▪ 주의: 병합하기 전 두 리스트는 이미 정렬되어 있어야 함.

            즉, Recursion을 이용해서 해당 두 리스트도 Merge sort 방식으로 정렬해야 함!

 

▪ 특징 :

Memory Complexity는

Time Complexity는

 

 

(예)

정렬된 두 리스트

첫번째 수: 30 vs 2 → 2가 작으므로 2는 병합리스트 맨 앞에 위치.

 

 

 

남은 30과 리스트2의 두번째 수 50 비교 →  30 < 50

→  30이 2 다음으로 위치함.

 

 

 

 

70 vs 50 →  70 > 50 →  50 정렬됨.

 

 

 

이런 식으로 계속 정렬을 진행하면, 

아래와 같은 결과가 나옴!!

 

 

 

 

 

 

from typing import List
# L: 정렬할 대상, start: 시작인덱스, end: 끝인덱스
def mergeHelp(L: List, start: int, end: int) -> None:
    if start == end:
        return None
        
    else:
    	# mid: 중간인덱스. 리스트를 2개로 나눌 때 2번째 리스트이 시작점 설정 위해 구함.
        mid = (start+end)//2      # mid = start + (end-start)//2 로 할 수도 있음.
        mergeHelp(L, start, mid)
        mergeHelp(L, mid+1, end)
        merge(L, start, mid, end)
    return L

# s: 시작인덱스, m: 중간인덱스, e: 끝인덱스
def merge(L: List, s: int, m: int, e: int) -> List:
    idx = s               #병합리스트에 값을 넣기 위해 필요. 
    subL1 = L[s:m+1]
    subL2 = L[m+1:e+1]
    i = j = 0
    while i<len(subL1) and j<len(subL2):
        if subL1[i] <= subL2[j]:
            L[idx] = subL1[i]
            i += 1
        else:
            L[idx] = subL2[j]
            j += 1
        idx += 1
        
    if j !=len(subL2):
        L[idx:e+1] = subL2[j:]
    elif i !=len(subL1):
        L[idx:e+1] = subL1[i:]
    return L


x = [100, 744, 1,10,77,5, 8, 3, 4]
mergeHelp(x, 0, len(x)-1)
# 답: [1, 3, 4, 5, 8, 10, 77, 100, 744]