합병 정렬 (Merge Sort) 란?

합병 정렬이란 ?

합병? 병합? 둘 다 사용해도 되는 정렬 이름이다.

- 합병 : A와 B가 합쳐져서 C가 만들어진다.

- 병합 : A가 B의 일부가 되거나? B가 A의 일부가 됨.

분할을 이용하는 분할 정복 알고리즘이다. 

말 그대로인 배열을 쪼개서 길이가 1인 배열을 만들고, 그 이후 정렬하면서 합치는 정렬이다.

합병은 binary tree 형태로 쪼개지기 때문에 가질 수 있는 최대 깊이는 log N이 된다.

 

병합 정렬의 단계가 존재하는데,

'분할, 정복, 결합' 3가지로 나누어 볼 수가 있다.

분할 단계 : 입력된 배열을 같은 크기의 2개의 부분 배열로 분할한다.

정복 단계 : 부분 배열을 정렬한다. (*여기서 부분 배열의 크기가 충분히 작지 않다면? '순환 호출'을 이용하여 다시 분할 정복법을 적용한다)

결합 단계 : 정렬된 부분 배열을 다시 하나의 배열로 결합한다.

* 단순히 중간 인덱스를 찾아야하는 분할 비용보다 모든 값들을 비교해야하는 병합 비용이 크다.

 

 

병합 정렬 장단점은 ?

장점 :

1. 데이터 분포에 영향을 덜 받는다. 즉, 입력 데이터가 크던 작던 정렬되는 시간은 동일하다 [O(nlogN)으로 동일]

2. 만약 레코드를 LinkedList 로 구성하면, Link Index 만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다. 즉, 어떠한 정렬 방법보다도 LinkedList 를 사용한 합병정렬 효율이 뛰어나다.

단점 :

1. 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다 (제자리 정렬이 아니다)

2. 레코드들의 크기가 큰 경우에는 이동 횟수가 많아지므로 매우 시간 복잡도가 올라간다.

 

시간 복잡도는 ?

분할 단계  =>  비교연산이나 이동연산이 수행되지 않는다. O(nlogN)

병합 단계(정복+결합) => 순환 호출의 깊이 만큼 합병단계 * 각 합병 단계의 이동연산 시. O(2nlogN)

따라서, O(3nlogN) = O(nlogN) 이다.

 

 

 

 

위키피디아