Desperate Undergraduate!Desperate Undergraduate!

asd

Merge Sort는 Divide and Conquer Approach의 일종으로 크게 3단계로 실행 된다.(2-Way Merge Sort 기준)

1. 리스트를 이등분 한다.(Divide)
2. 이등분된 리스트 두개를 정렬한다.(Conquer)
3. 이등분된 리스트를 병합하여 하나의 리스트로 만든다.(Combie)

다음은 Merge Sort를 C언어로 구현한 것이다.

(소스 생략)

(예제 생략)

Divide and Conquer Approach를 보면 Binary Search와 2-Way Merge Sort와 같이 세 개가 아닌 두 개를 사용하는 경우가 많다. 왜 두개를 사용하는가?

K-Way Merge Sort를 예로 들어 보면 K값을 3으로 할 수도 있고 2로 할 수도 있다. 2-Way Merge Sort와 3-Way Merge Sort의 시간복잡도(Time Complexity)를 생각해 보아야 한다. Divide and Conquer Approach의 경우 T(n) = Divide + Conquer + Combie 시간을 생각해 보아야 한다.

K = 2 인 경우, T(n) = 0 + T(n/2) + T(n/2) + n/2 + n/2 - 1

K = 3 인 경우, T(n) = 0 + T(n/3) + T(n/3) + T(n/3) + n/3 + n/3 + n/3 - 1

결국 입력 원소의 개수가 크다면 K 값이 큰 것이 되부름(Recursion)을 적게 하여 유리하다. 또한 병렬 처리를 할 경우 K 값이 큰 것이 좋다. 하지만 3-Way Merge Sort는 병합 과정이 복잡하기 때문에 메모리의 Activation Record를 낭비해서라도 2-Way Merge Sort를 사용한다.