[기술면접/알고리즘] Merge Sort

Merge Sort에 대해 설명하세요

Keyword

분할 정복, 분할, 재귀, 합병

---

Script

합병 정렬은 분할 정복 알고리즘을 기반으로 한 정렬 알고리즘으로, 입력 배열을 같은 크기의 2개의 부분 배열로 분할하는데, 이 때 부분 배열의 크기가 최소가 될 때까지 재귀적으로 반복합니다. 그리고 정렬된 부분 배열을 합병하면서 정렬을 수행하며 배열을 완성시킵니다. 시간복잡도는 최선,평균,최악 모두 O(nlogn)입니다.

---

Additional

시간복잡도

비교 횟수
분할 단계
비교/이동 연산 수행 X

합병 단계
재귀 호출의 깊이 = logN
각 깊이 당 비교 횟수 = n

=> 순환 호출 깊이 만큼의 합병 단계 * 각 합병 단계의 비교 연산 = nlogn

이동 횟수
재귀 호출의 깊이 = logN
각 합병 단계의 이동 연산 = n

=> 재귀 호출의 깊이 * 각 합병 단계의 이동 연산 = nlogn

T(n) = nlogn

그림

전체

합병 단계

코드 (python)

def merge_sort(arr):
    def sort(low, high):
        if high - low < 2:
            return
        mid = (low + high) // 2
        sort(low, mid)
        sort(mid, high)
        merge(low, mid, high)

    def merge(low, mid, high):
        temp = []
        l, h = low, mid

        while l < mid and h < high:
            if arr[l] < arr[h]:
                temp.append(arr[l])
                l += 1
            else:
                temp.append(arr[h])
                h += 1

        while l < mid:
            temp.append(arr[l])
            l += 1
        while h < high:
            temp.append(arr[h])
            h += 1

        for i in range(low, high):
            arr[i] = temp[i - low]

    return sort(0, len(arr))

정렬 알고리즘 시간복잡도 비교