병합 정렬은 분할 정복(divide and conquer) 알고리즘을 사용하는 정렬 방식이다.
병합 정렬은 분할 정복(divide and conquer) 알고리즘의 하나이다.
문제를 작은 단위로 쪼갠 뒤 작은 문제부터 해결하여 큰문제를 해결한다.
병합 정렬의 과정은 다음과 같다.
1. 정렬되지 않은 초기 리스트(array[p..q]
)가 주어진다.
(p는 첫번째 인덱스, q는 마지막 인덱스)
2. 분할 :
r = p+q/2
의 계산 결과값을 내림하여 정수 r을 찾는다.3. 정복 : 분할된 두개의 하위 배열을 각각 재귀적으로 정렬한다.
4. 병합 : 정렬된 두개의 배열을 하나의 정렬된 배열로 결합한다.
탈출조건
2개 미만의 요소가 포함된 하위 배열
(요소가 하나도 없거나 하나만 있는 하위 배열은 이미 정렬되어 있는 것과 같다.)
시간복잡도
O(NlogN)