[자료구조] 병합 정렬(merge sort)....

[자료구조] 병합정렬(merge sort)[자료구조] 병합정렬(merge sort)
병합 정렬은 여러 개의 정렬된 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만드는 방법이다. 병합 정렬은 전체 원소들에 대해서 수행하지 않고 부분집합으로 분할하고 각 부분집합에 대해서 정렬 작업을 완성한 후에 정렬된 부분집합을 다시 결합하는 분할 정복 기법을 사용한다. 
 
 2개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법을 2-way 병합이라 하고, n개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법을 n-way 병합이라고 한다. 2-way 병합 정렬은 다음과 같은 작업을 반복 수행하면서 완성한다.

(1) 분할 : 입력 자료를 같은 크기의 부분집합 2개로 분할한다.

(2) 정복 ; 부분집합의 원소들을 정렬한다. 부분집합의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다.

(3) 결합 : 정렬된 부분집합들을 하나의 집합으로 통합한다.

병합 정렬은 각 단계에서 새로 병합하여 만든 부분집합을 저장할 공간이 추가로 필요하기 때문에 정렬할 원소 n개에 대해서 2xn개의 메모리 공간을 사용한다. n개의 원소를 분할하기 위해서 log₂n번의 단계를 수행하고, 부분집합의 원소를 비교하면서 병합하는 단계에서 최대 n번의 비교 연산을 수행하므로 전체 병합 정렬의 시간 복잡도는 O(nlog₂n )이 된다.

아래의 동영상을 보면 이해하기 쉬울 것이다.


[자료구조] 병합정렬(merge sort)[자료구조] 병합정렬(merge sort)