[알고리즘] merge sort algorithm analysis

Divide and Conquer, 효율적인 알고리즘 설계 : Merge Sort 분석

서론

알고리즘 설계 패러다임 중 하나인 '분할 정복(Divide and Conquer)'은 문제를 작은 부분 문제로 나누어 해결하고, 이들의 결과를 결합하여 원래 문제의 답을 얻는 전략이다. 마치 복잡한 퍼즐을 작은 조각으로 나누어 맞추는 것처럼, 분할 정복은 효율적인 알고리즘 설계에 널리 활용된다. 이번 포스팅에서는 분할 정복의 대표적인 예시인 Merge Sort 알고리즘을 자세히 살펴보고, 정확성 증명과 실행 시간 분석을 통해 그 효율성을 확인해보자.

Merge Sort 알고리즘

Merge sort flow

Merge Sort는 이름에서 알 수 있듯이, '합병(Merge)'을 통해 정렬을 수행하는 알고리즘이다. 먼저 리스트를 절반으로 나누는 '분할(Divide)' 과정을 거친 후, 각 부분 리스트를 재귀적으로 정렬한다. 마지막으로 정렬된 두 부분 리스트를 하나의 정렬된 리스트로 합치는 '정복(Conquer)' 과정을 통해 전체 리스트를 정렬한다.

Python
def mergesort(A): #list의 요소가 1개만 있을 때까지 재귀적 실행
  if len(A) <= 1:
    return A
  mid = len(A) // 2
  left = mergesort(A[:mid])
  right = mergesort(A[mid:])
  return merge(left, right)

def merge(left, right):
  result = []
     i, j = 0, 0
  while i < len(left) and j < len(right): #작은 요소부터 result에 추가(정렬)
    if left[i] <= right[j]:
      result.append(left[i])
      i += 1
    else:
      result.append(right[j])
      j += 1
  result.extend(left[i:])
  result.extend(right[j:])
  return result   

Correctness: 수학적 귀납법을 통한 분석

Merge Sort의 정확성은 수학적 귀납법을 통해 증명할 수 있다. 이때 귀납의 대상은 입력 리스트의 길이가 된다.

귀납 가설: 길이가 i인 입력 리스트에 대해 Merge Sort는 정확하게 정렬된 결과를 반환한다.
기본 경우 (i=1): 길이가 1인 리스트는 이미 정렬된 상태이므로, Merge Sort는 이를 그대로 반환한다. 따라서 기본 경우는 자명하게 참이다.
귀납 단계: 길이가 1부터 i까지의 모든 리스트에 대해 Merge Sort가 정확하게 동작한다고 가정하자. 길이가 i+1인 리스트를 Merge Sort에 입력하면, 먼저 리스트를 두 부분 리스트로 나눈다. 각 부분 리스트의 길이는 i 이하이므로, 귀납 가설에 의해 재귀 호출을 통해 정렬된 결과를 얻을 수 있다. 마지막으로 merge 함수는 정렬된 두 부분 리스트를 합쳐 정렬된 전체 리스트를 생성한다. 따라서 길이가 i+1인 리스트에 대해서도 Merge Sort는 정확하게 동작한다.
결론: 수학적 귀납법에 의해, 임의의 길이 n에 대해 Merge Sort는 정확하게 정렬된 결과를 반환한다.

Runtime: Recurrence Relation과 master method

Merge Sort의 실행 시간을 분석하기 위해, 입력 리스트의 길이 n에 대한 실행 시간을 T(n)이라고 정의하자. Merge Sort는 다음과 같은 점화식으로 표현할 수 있다.

T(n) = 2T(n/2) + O(n) (n > 1)
T(1) = O(1)

이는 리스트를 절반으로 나누는 데 O(1), 각 부분 리스트를 정렬하는 데 2T(n/2), 그리고 합병하는 데 O(n)의 시간이 걸리기 때문이다. 이 점화식을 풀기 위한 몇 가지 방법을 살펴보자.

1. Recursion Tree Method

Recursion Tree를 통해 점화식을 시각적으로 표현하고, 각 레벨에서 수행되는 작업량과 전체 레벨 수를 통해 실행 시간을 분석한다. Merge Sort의 Recursion Tree는 다음과 같다.

Recursion Tree

루트 노드: 입력 리스트 전체에 대한 Merge Sort 호출 (작업량: cn)
다음 레벨: 두 개의 부분 리스트에 대한 Merge Sort 호출 (각 작업량: cn/2)
...
마지막 레벨: n개의 길이 1인 리스트에 대한 Merge Sort 호출 (각 작업량: c)

각 레벨의 작업량은 cn으로 동일하며, 트리의 높이는 log₂n이다. 따라서 전체 실행 시간은 O(n log n)이다.

2. Iteration Method

Iteration Method는 점화식을 반복적으로 적용하여 패턴을 찾고, 이를 통해 실행 시간을 분석한다.

T(n) ≤ 2T(n/2) + cn
     ≤ 2(2T(n/4) + cn/2) + cn = 4T(n/4) + 2cn
     ≤ 4(2T(n/8) + cn/4) + 2cn = 8T(n/8) + 3cn
    ...
     ≤ 2^k T(n/2^k) + kcn

n / 2^k = 1일 때, 즉 k = log₂n일 때까지 반복하면,

T(n) ≤ nT(1) + cn log₂n 
≤ cn + cn log₂n 
= O(n log n)

3. Master Method

마스터 정리는 특정 형태의 점화식을 쉽게 풀 수 있도록 도와주는 정리이다. 이 때 특정 형태란, 전체 problem에서 모든 sub-problem이 같은 size를 갖는 것을 말한다.

Master method

Merge Sort의 점화식은 sub-problem이 n/2된 형태로 같으므로 마스터 정리의 형태에 해당하며, a = 2, b = 2, d = 1이다. a = b^d 이므로, 마스터 정리에 의해 실행 시간은 O(n log n)이다.

4. Substitution Method

Substitution Method는 결과를 추측하고, 수학적 귀납법을 통해 추측이 맞는지 증명하는 방법이다. Merge Sort의 실행 시간이 O(n log n)이라고 추측하고, 이를 증명해보자.

귀납 가설: k < n인 모든 k에 대해 T(k) ≤ ck log k라고 가정한다. (c는 상수)
기본 경우: T(n/2)을 대체하여 T(n) ≤ cn log n 임을 보인다.

귀납 단계:

T(n) 
≤ 2T(n/2) + cn 
≤ 2(c(n/2) log(n/2)) + cn (귀납 가설 적용)
= cn log(n/2) + cn 
= cn log n - cn log 2 + cn
= cn log n - cn + cn
= cn log n

결론: 수학적 귀납법에 의해, T(n) ≤ cn log n이므로, Merge Sort의 실행 시간은 O(n log n)이다.

결론

분할 정복 패러다임을 사용하는 Merge Sort 알고리즘은 효율적인 정렬 알고리즘 중 하나이며, 시간 복잡도는 O(n log n)이다. 이는 지난 시간에 알아본 Insertion Sort의 최악 시간 복잡도인 O( $n^{2}$ )보다 빠르므로, 더 큰 입력에 대해 효율적으로 동작한다. 또한, Merge Sort는 안정적인 정렬 알고리즘이며, 외부 정렬에도 활용될 수 있다는 장점이 있다. 하지만 추가적인 메모리 공간이 필요하다는 단점도 존재한다. 이처럼 알고리즘의 정확성 증명과 실행 시간 분석은 알고리즘의 성능과 효율성을 이해하는 데 중요한 역할을 하니 알아두자.

추천글 :

[알고리즘] Algorithmic Analysis - correctness with induction
(https://hyeonb.blogspot.com/2024/09/algorithmic-analysis-correctness-with.html)

[알고리즘] Algorithmic analysis - runtime with asymptotic analysis
(https://hyeonb.blogspot.com/2024/09/algorithmic-analysis-runtime-with.html)