분할 정복 알고리즘
병합 정렬은 데이터를 계속 반으로 쪼개고 원소들을 다시 합치며 정렬
예로 1 9 8 4 3 5 2 7 이라는 8개의 숫자를 오름차순으로 정렬시켜보자.
먼저 절반으로 나눈다.
1 9 8 4 | 3 5 2 7
아직 더 나눌 수 있으므로 다시 반씩 나눈다.
1 9 | 8 4 | 3 5 | 2 7
여기서 마지막으로 한 번 더 나누면 원소가 하나씩이 된다.
1 | 9 | 8 | 4 | 3 | 5 | 2 | 7
더 이상 나눌 수 없으므로 병합을 시작한다. 먼저 1과 9를 보자. 1이 9보다 작으므로 그대로 병합된다. 이 때 추가적인 메모리를 추가하여 거기에 병합하며 담기 시작한다.
1 9 |
8 과 4를 병합하면 4가 앞으로 오며 병합될 것이다.
1 9 | 4 8
이제 위 두 그룹을 병합한다. 가장 먼저 각 그룹의 첫 번째를 비교한다. 1이 작으므로 앞에 위치 한다.
1 O O O
이제 9와 4를 비교하여 4를 다음에 위치시킨다.
1 4 O O
마찬가지로 9와 8을 비교하여 8과 9 순서로 위치시켜 병합시킨다.
1 4 8 9
남은 오른쪽 네 개의 숫자도 동일한 과정을 거친다.
1 4 8 9 | 2 3 5 7
이제 구해진 각4개의 숫자들을 비교하여 병합한다. 다른 메모리 공간에 1과 2를 비교하여 1을 앞에 위치시키고, 4와 2를 비교하여 2를 위치시키고, 4와 3을 비교하고.. 이런 식으로 반복하고 나면 다음과 같이 정렬이 완료된다.
1 2 3 4 5 7 8 9
전체 과정을 요약하여 보면 다음과 같다.
1 | 9 | 8 | 4 | 3 | 5 | 2 | 7 : 가장 작은 단위로 나눠짐.
1 9 | 4 8 | 3 5 | 2 7 : 한 개씩이 정렬되어 병합됨.
1 4 8 9 | 2 3 5 7 : 두 개씩이 정렬되어 병합됨.
1 2 3 4 5 7 8 9 : 네 개씩이 정렬되어 병합됨.
총 연산횟수는 NlogN
복잡도의 상한은 O(n log n)이며 하한시간도 마찬가지로 Ω(n log n)