본문 바로가기

3. 알고리즘 공부

[426] 병합 정렬(Merge Sort)

1. 병합 정렬 개념

존 폰 노이만이 1945년에 개발한 정렬 알고리즘입니다.

분할 정복(Divide and Conquer) 기법을 사용한 알고리즘으로 시간 복잡도가 \(O(n\log{n})\)입니다.

 

주어진 배열을 n개의 부분 배열로 분할하여 재귀적으로 정렬하는 방식으로, 일반적으로 2개의 부분 배열로 나눕니다.

이후 나누어진 부분 배열을 다시 합하는 과정에서 정렬된 배열을 임시로 저장할 메모리 공간이 필요하여 공간 복잡도는 \(O(n)\)입니다.

 

주어진 배열을 나누는 횟수는 (\(\log_2{n}\)) 번 일어나고, 병합될 때 정렬하는 과정에서 \(O(n)\)의 시간이 걸리므로 시간 복잡도는 항상 \(O(n\log{n})\)이 됩니다.

 

https://ko.wikipedia.org/wiki/합병_정렬

 

합병 정렬 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 합병 정렬 또는 병합 정렬(영어: merge sort 머지 소트[*])은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며,

ko.wikipedia.org

2. 병합 정렬 예제

3. 병합 정렬 코드

nums = [6, 1, 2, 5, 8, 3, 4, 7]

def merge_sort(left, right, nums):
    if left == right:
        return
    
    # 분할(divide)
    mid = (left+right)//2
    
    # 정복(conquer)
    merge_sort(left, mid, nums)
    merge_sort(mid+1, right, nums)

    # 결합(combine)
    if nums[mid] <= nums[mid+1]: # 이미 정렬이 되어 있으면 통과
        return
    
    tmp = [] # 임시 배열에 정렬된 두 부분 배열을 결합
    l, r = left, mid+1
    for _ in range(right-left+1):
        if r > right:
            tmp.append(nums[l])
            l += 1
        elif l > mid:
            tmp.append(nums[r])
            r += 1
        elif nums[l] <= nums[r]:
            tmp.append(nums[l])
            l += 1
        else:
            tmp.append(nums[r])
            r += 1

    j = 0
    for i in range(left, right+1):
        nums[i] = tmp[j] # 원래의 배열에 임시 배열을 덮어쓰기
        j += 1


merge_sort(0, len(nums)-1, nums)
print(nums)
# [1, 2, 3, 4, 5, 6, 7, 8]

4. 병합 정렬 장점

병합 정렬은 안정적인 정렬입니다. 따라서 동일한 값을 가지는 원소는 상대적인 순서가 정렬 후에도 변하지 않습니다.

병합 정렬은 최선, 최상, 평균 시간 복잡도가 모두 \(O(n\log{n})\)으로 데이터에 관계 없이 일관된 성능을 보장합니다.

외부 정렬(External Sorting)로 사용할 수 있어서 메모리 제한이 있는 환경에서 대규모 데이터를 처리할 수 있습니다.

연결 리스트를 정렬하는 경우, 제자리 정렬로 구현이 가능하여 추가적인 메모리가 거의 들지 않습니다.

5. 병합 정렬 단점

병합 과정에서 임시 배열을 사용하기 때문에 공간 복잡도가 \(O(n)\)으로 추가적인 메모리 공간을 필요로 합니다.(제자리 정렬이 아닙니다.)

병합 과정에서 데이터의 이동이 빈번하게 일어나기 때문에 속도가 떨어집니다.

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

정렬 알고리즘 최악(Worst) 최선(Best) 평균(Average)
버블 정렬(Bubble Sort) \(O(n^2)\) \(O(n^2)\) \(O(n^2)\)
선택 정렬(Selection Sort) \(O(n^2)\) \(O(n^2)\) \(O(n^2)\)
삽입 정렬(Insertion Sort) \(O(n^2)\) \(O(n)\) \(O(n^2)\)
퀵 정렬(Quick Sort) \(O(n^2)\) \(O(n\log{n})\) \(O(n\log{n})\)
병합 정렬(Merge Sort) \(\boldsymbol{O(n\log{n})}\) \(\boldsymbol{O(n\log{n})}\) \(\boldsymbol{O(n\log{n})}\)
힙 정렬(Heap Sort) \(O(n\log{n})\) \(O(n\log{n})\) \(O(n\log{n})\)
기수 정렬(Radix Sort) \(O(n)\) \(O(n)\) \(O(n)\)
계수 정렬(Counting Sort) \(O(n)\) \(O(n)\) \(O(n)\)