[Algorithm] 병합 정렬 (Merge Sort) 알고리즘

병합 정렬

• 분할 정복 (Divide and Conquer) 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하여 합치는 알고리즘
• 시간복잡도 : O(nlogn)

핵심 이론

 

• 왜 시간복잡도가 O(nlogn)인가?

그림에서는 데이터의 개수가 8.

정렬 3번(log 8)만에 정렬된 데이터가 나옴

N번의 데이터 엑세스가 log n번 일어나기 때문에 시간복잡도가 O(nlogn)이다.

 

• 수행 방식

1. 그림에서 최초로는 8개의 그룹으로 나눈다.

2. 2개씩 그룹을 합치며 오름차순으로 정렬한다.

-> (32,42), (24,60), (5,15), (45,90)

3. 2개씩 그룹을 합치며 다시 오름차순으로 정렬한다.

-> (24,32,42,60) , (5,15,45,90)

.

.

.

 이런 식으로 병합 정렬 과정을 거친다.

 

 

2개의 그룹을 병합하는 과정 (중요!)

• 투 포인터 개념을 사용해 왼쪽, 오른쪽 그룹을 병합한다.
• 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동한다.

수도코드 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))

 

 

• 참고자료

https://www.daleseo.com/sort-merge/

[알고리즘] 병합 정렬 - Merge Sort (Python, Java)

https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC&unitId=148380