Merge Sort (병합정렬)

Merge Sort (병합정렬)

병합정렬은 대표적인 분할 정복 알고리즘(Divide and conquer algorithm)입니다.

정렬되지 않은 리스트를 하나의 원소만 포함하는 n개의 리스트로 분할한 후 부분 리스트가 하나만 남을 때까지 반복해서 병합하여 정렬합니다.

N개의 크기의 배열을 logN의 단계로 정렬을 수행해 NlogN의 시간복잡도를 가집니다.

Merge Sort 정렬 과정

초기상태: [3 5 6 1 2 4 0 7]

1. 하나의 큰 리스트를 하나의 원소만 포함하는 8개의 리스트로 분할합니다.[3 5 6 1] [2 4 0 7][3] [5] [6] [1] [2] [4] [0] [7]
2. [3 5] [6 1] [2 4] [0 7]
3. [3 5 6 1 2 4 0 7]
4. 하나의 리스트가 남을때까지 병합하면서 정렬합니다.[3 5] [1 6] [2 4] [0 7][0 1 2 3 4 5 6 7]
5. [1 3 5 6] [0 2 4 7]
6. [3] [5] [6] [1] [2] [4] [0] [7]

Merge Sort 코드 (python)

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

    def merge(start, mid, end):
        temp = []
        left, right = start, mid

        while left < mid and right < end:
            if arr[left] < arr[right]:
                temp.append(arr[left])
                left += 1
            else:
                temp.append(arr[right])
                right += 1

        while left < mid:
            temp.append(arr[left])
            left += 1

        while right < end:
            temp.append(arr[right])
            right += 1

        for i in range(start, end):
            arr[i] = temp[i-start]

    sort(0, len(arr))


if __name__ == "__main__":
    import random
    total_elements = 100
    arr = random.sample(range(0, total_elements, total_elements)
    merge_sort(arr)