IT용어위키

머지 소트(Merge Sort)는 분할 정복(divide and conquer) 방식의 정렬 알고리즘으로, 데이터를 반으로 나누어 정렬한 후 병합하는 방식으로 동작한다. 안정 정렬(stable sort)에 속하며, 평균 및 최악의 경우 시간 복잡도가 O(n log n)으로 일정하다. (Θ(n log n)

개요

머지 소트는 문제를 작은 부분으로 나누고, 이를 정렬한 후 병합하는 방식으로 동작한다. 알고리즘의 동작 과정은 다음과 같다.

리스트를 반으로 나눈다.
각각의 부분 리스트를 재귀적으로 정렬한다.
정렬된 두 리스트를 병합하여 하나의 정렬된 리스트를 만든다.

이 알고리즘은 재귀적으로 구현될 수도 있고, 반복문을 사용한 비재귀적(반복문) 방식으로도 구현될 수 있다.

알고리즘 과정

머지 소트의 동작 과정은 다음과 같다.

1. 분할 (Divide)

주어진 리스트를 두 개의 하위 리스트로 분할한다.
리스트의 크기가 1이 될 때까지 재귀적으로 나눈다.

예제: 정렬할 배열이 다음과 같다고 가정한다.

[38, 27, 43, 3, 9, 82, 10]

이 배열을 반으로 나누면 다음과 같이 된다.

[38, 27, 43, 3]    [9, 82, 10]

이 과정을 계속 반복하면, 모든 부분 배열의 크기가 1이 될 때까지 나눠진다.

[38] [27] [43] [3] [9] [82] [10]

2. 정복 (Conquer)

각각의 하위 리스트를 개별적으로 정렬한다.

정렬된 두 개의 리스트를 병합하며 정렬을 수행한다.

1단계 병합 후:

[27, 38] [3, 43] [9, 10] [82]

2단계 병합 후:

[3, 27, 38, 43] [9, 10, 82]

3. 병합 (Merge)

두 개의 정렬된 리스트를 하나의 정렬된 리스트로 합친다.

최종 병합 과정 후:

[3, 9, 10, 27, 38, 43, 82]

이제 전체 리스트가 정렬되었다.

시간 복잡도

머지 소트의 시간 복잡도는 다음과 같이 분석할 수 있다.

최선의 경우(Best Case) : Ω(n log n)
평균적인 경우(Average Case) : Θ(n log n)
최악의 경우(Worst Case) : O(n log n)

머지 소트는 항상 O(n log n)의 시간 복잡도를 보장하며, 입력이 어떠한 순서로 되어 있더라도 성능이 일정하다.

공간 복잡도

머지 소트는 추가적인 메모리 공간이 필요하며, 재귀 호출과 병합 과정에서 O(n)의 추가 공간을 사용한다.

구현

다음은 파이썬(Python)으로 구현된 머지 소트 예제이다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half)

def merge(left, right):
    sorted_arr = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1

    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])
    return sorted_arr

# 사용 예제
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)  # 출력: [3, 9, 10, 27, 38, 43, 82]

머지 소트의 특징

안정 정렬(Stable Sort) : 동일한 값의 원소들이 정렬 후에도 상대적인 순서를 유지한다.
일관된 성능 : 최선, 평균, 최악의 경우 시간 복잡도가 O(n log n)으로 일정하다.
추가적인 메모리 사용 : 병합 과정에서 추가적인 메모리 공간이 필요하여 O(n)의 공간 복잡도를 가진다.
큰 데이터 정렬에 유리 : 퀵 정렬과 달리 최악의 경우에도 O(n log n)을 유지하여 안정적인 성능을 제공한다.

응용

머지 소트는 다음과 같은 상황에서 유용하게 사용된다.

연결 리스트(Linked List) 정렬 - 연결 리스트에서는 추가적인 메모리 사용이 상대적으로 적어 퀵 정렬보다 유리할 수 있음.
외부 정렬(External Sorting) - 데이터가 메모리에 한 번에 적재되지 않을 때 사용됨.

같이 보기

참고 문헌

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
Knuth, D. E. (1997). The Art of Computer Programming. Addison-Wesley.