[APS] 12. 병합정렬(합병정렬) Merge Sort

1. 합병 정렬의 기본적인 idea

---

list가 주어지면 → 길이가 1일 때까지 나눈다 분할 → 병합 merge !

2. 분할 → python 으로 구현하기

---

def merge_sort(unordered_list):
    if len(unordered_list) <= 1: # list의 길이를 더이상 쪼갤 수 없을 때까지 쪼갠다.
        return unordered_list
    middle = len(unordered_list) // 2 # 가운데 원소를 중심으로 좌, 우 리스트로 나눈다.
    left = unordered_list[:middle]
    right = unordered_list[middle:]

    left = merge_sort(left) # recursion으로 반복 진행한다.
    right = merge_sort(right)

    return merge(left, right) # 쪼개고 난 후 병합을 진행한다.

3. 병합 → python 으로 구현하기

---

def merge(leftlist, rightlist):
    i, j = 0, 0 # i는 leftlist의 index, j는 rightlist의 index
    sorted_list = [] # 반환할 정렬된 리스트

    while i < len(leftlist) or j < len(rightlist):
        if i < len(leftlist) and j < len(rightlist):
            if leftlist[i] < rightlist[j]:
                sorted_list.append(leftlist[i])
                i += 1
            else:
                sorted_list.append(rightlist[j])
                j += 1

        elif i < len(leftlist):
            sorted_list.append(leftlist[i])
            i += 1

        elif j < len(rightlist):
            sorted_list.append(rightlist[j])
            j += 1

    return sorted_list

a = [ 3, 4, 7, 1, 2, 10, 5, 6, 9 ]
print(merge_sort(a)) # [1, 2, 3, 4, 5, 6, 7, 9, 10]

Uploaded by N2T