이 글은 칸아카데미-알고리즘 공부를 요약한 글입니다.
하위 문제의 결정
병합 정렬은 정렬 과정에서 분할 정복 알고리즘을 사용합니다. 때문에 하위 문제를 결정해야합니다. 보통 정렬이라 하면 array[0...n-1]의 배열을 정렬함을 의미합니다. 편의상 array[0···n-1]의 배열을 array[p...r]이라고 표시하겠습니다.
그럼 분할 정복 알고리즘을 가지고 병합 정렬을 어떻게 하는지 살펴보겠습니다.
1. 분할: array[p...r]에서 p와 r의 중간인 q를 찾습니다. 이진 검색에서 중간점을 찾았던 것과 마찬가지로 p와 r을 더하여 2로 나눈 뒤 내림하여 정수로 만들겠습니다.
2. 정복: 분할 단계에서 만들어진 두 하위 문제 각각의 하위 배열을 재귀적으로 정렬합니다. 즉 array[p...q]와 array[q+1...r]을 재귀적으로 정렬하게 됩니다.
3. 결합: 정렬된 두 하위 배열을 하나의 정렬된 배열인 array[p...r]로 결합시킵니다.
탈출조건은 무엇일까요?
탈출조건은 array[p...r]에서 p가 r과 같거나 클 때 이는 배열의 크기가 한 개 혹은 하나도 없다는 의미입니다. 이는 이미 정렬되어 있다고 봐도 됩니다. 그러므로 p가 r보다 작을 때만 분할-정복-결합의 과정을 거치게 됩니다.
예제
[14, 7, 3, 12, 9, 11, 6, 2] 의 배열이 있습니다. 여기서 array[p...r]과 대응하면 array[0...7]로서 p=0, r=7이됩니다. 이를 하위 배열로 만들어보면 탈출 조건이 맞지 않는 하위 문제가 만들어집니다. (array[0...3], array[4...7])
· 분할 단계에서 q = 3 이 됩니다.
· 정복 단계에서 [14, 7, 3, 12] 값의 array[0..3]과 [9, 11, 6, 2]가 포함된 array[4..7]을 정렬합니다. 정복 단계가 끝나면 이 두 하위 배열은 정렬이 된 상태이기 때문에 각각 array[0..3] = [3, 7, 12, 14], array[4..7] = [2, 6, 9, 11] 로 정렬이 되어 있습니다. 고로 완전한 배열은 [3, 7, 12, 14 / 2, 6, 9, 11] 이 되겠습니다.
· 결합 단계에서 앞서 정렬한 하위 배열을 병합합니다. 마지막으로 배열 [2, 3, 6, 7, 9, 11, 12, 14] 를 얻게 됩니다.
그럼 정복 단계에서 하위 배열인 array[0..3]은 어떻게 정렬된걸까요? 우선 array[0..3]은 p<r 이기 때문에 여전히 탈출 조건이 아닙니다. 이를 다시 하위 문제로 분할 하면 array[0..1] = [14, 7] 과 array[2..3] = [3, 12]이 되며 이는 탈출 조건에 부합하며, 이를 병합하면 [3, 7, 12, 14]가 됩니다.
그림 - 구현 과정
병합 정렬에 대해서 알아봤습니다. 병합 정렬의 대부분의 과정은 복잡하지 않기 때문에 이해하기 쉽습니다. 탈출 조건을 확인하는 것도 간단하며, 분할 단계에서 q값을 찾기도 쉽습니다. 정복 단계에서는 재귀 호출을 두 번 시켜주면 됩니다. 그리고 실제로 정렬이 되는 곳은 결합 단계입니다.
이상 병합 정렬 기본 개념이었습니다. 다음엔 심화 문제를 풀어보겠습니다.