[Algorithm] Divide and Conquer - Merge sort

Divide and conquer

 

대표적인 알고리즘의 갈래 중 하나인 분할 정복은, 하나의 커다란 문제를 여러 작은 문제로 나눈 후 (Divide), 작은 문제를 해결하고 나서 다시 합쳐 (Combine) 해결하는 (Conquer) 방법이다.

 

Insertion sort

 

분할 정복이 주는 이점이 무엇일까? 그걸 알아보기 전에 앞서 배웠던 삽입 정렬 (Insertion sort)을 생각해보자. 삽입 정렬은 incremental approach로, 모든 요소를 순차적으로 방문하는 방식을 택한다. 그러다 보니 input instance의 (이미) 정렬된 정도에 따라 최소 Ω(n)에서 최대 O(n²)의 시간 복잡도를 지니게 된다. 그렇다면 mergesort의 시간 복잡도는 어떨까? 결론부터 말하자면 O(n lg n)의 시간 복잡도를 지닌다. 

 

Steps

 

앞서 살짝 설명했던 Divide, Combine, 그리고 Conquer까지의 three step을 살펴보자.

 

Divide The problem into a number of subproblems that are smaller instances of the same problem

Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, just solve the subproblems in a straightforward manner.

Combine the solutions to the subproblems into the solution for the original problem.

 

Merge sort

 

그럼 이러한 분할 정복 알고리즘을 통해 merge sort는 어떤 순서로 작동하게 될까? 다음 그림을 보자.

 

 

y축을 본다면 가운데를 기준으로 위는 Divide에 해당하고, 각 요소의 길이가 1이 된 순간부터 다시 Combine을 시작한다. Combine을 하는 과정에서 Sorting을 진행한다. 그렇다면 각각의 과정에서 시간 복잡도는 어떻게 계산될까?

 

pseudo code

 

먼저 합치는 데에 걸리는 시간은 서로 다른 두 배열의 모든 요소를 서로 비교하며 정렬하기 때문에 Θ(n)의 시간이 소요된다. 추가적으로 MERGE(A, p, q, r)라는 의사 코드를 살펴보면, A라는 배열에 p ... q, q + 1 ... r의 두 배열을 비교하기 때문에 A 배열의 크기인 n = r - p + 1 만큼 정렬을 하게 된다.

 

 

이어서 MERGE-SORT의 경우를 살펴 보자. 이 함수는 요소의 개수를 반으로 나눠 재귀적으로 호출하고 있다. 따라서 Θ(lg n)의 시간이 소요된다. 한 번의 MERGE-SORT 실행 과정에서 MERGE 함수가 한 번씩 실행되고 있기 때문에, 따라서 merge sort의 시간 복잡도는 Θ(n lg n)이 된다.

 

Analyzing divide and conquer algorithms

 

분할 정복의 한 예시로써 합병 정렬을 살펴 보았다. 분할 정복을 일반화하면 다음과 같이 나타낼 수 있을 것이다.

 

$$T(n) = \begin{cases} \Theta(1) & \text{if } n \leq c , \\ aT(n/b) + D(n) + C(n) & \text{otherwise .} \end{cases} $$

 

해당 수식에서 D는 나누는 데에 걸리는 시간, C는 합치는 데에 걸리는 시간을 의미한다. 그렇다면 합병 정렬에서의 a, b 값, 그리고 Divide와 Combine의 시간 복잡도는 어떻게 될까?

 

$$ T(n) = \begin{cases} \Theta(1) & \text{if } n = 1 , \\ 2T(n/2) + \Theta(n) & \text{if } n > 1 . \end{cases} $$

 

다음과 같다. 주어진 배열을 반으로 나누고 그 둘을 다시 재귀적으로 실행하기 때문에 a와 b 모두 2를 가진다. 이어서 Divide에 걸리는 시간은 단순히 배열의 중간 인덱스를 구하는 상수 시간이 소요되기 때문에 Θ(1), 마지막으로 합치는 데에는 위에서 살펴보았던 MERGE 함수의 경우로 Θ(n)의 시간이 소요된다. Divide의 경우, Combine에 묻혀 생략해줄 수 있다.