병합(Merge) 알고리즘이란?
병합(Merge) 알고리즘은 두 개의 정렬된 리스트를 하나의 정렬된 리스트로 합치는 알고리즘입니다. 이 알고리즘은 다양한 상황에서 활용되며, 특히 병합 정렬(Merge Sort)을 수행할 때 정렬된 작은 리스트들을 점점 더 큰 리스트로 합치는 핵심 과정에 사용됩니다.
동작 원리
병합 알고리즘의 접근 방식은 매우 단순합니다. 두 개의 리스트와 각 리스트를 가리키는 두 개의 포인터(pointer)를 준비합니다. 첫 번째 포인터는 첫 번째 리스트의 요소를, 두 번째 포인터는 두 번째 리스트의 요소를 가리킵니다.
이후 다음과 같은 방식으로 진행됩니다.
1. 두 포인터가 가리키는 값을 서로 비교합니다.
2. 더 작은 값을 가진 요소를 결과 리스트로 가져옵니다.
3. 요소를 가져온 리스트의 포인터를 한 칸 앞으로 이동시킵니다.
4. 두 리스트 중 하나가 모두 소진될 때까지 위 과정을 반복합니다.
5. 마지막으로, 아직 요소가 남아 있는 리스트의 나머지 값들을 최종 병합 리스트의 끝에 그대로 추가합니다.
두 입력 리스트가 이미 정렬되어 있기 때문에 매번 '더 작은 값'만 선택해도 자연스럽게 전체가 정렬된 결과를 얻을 수 있다는 점이 이 알고리즘의 핵심 아이디어입니다.
알고리즘 동작 예시
아래 그림을 통해 두 리스트가 하나로 병합되는 과정을 더 직관적으로 이해할 수 있습니다.
알고리즘 의사코드(Pseudocode)
Merge(array, left, middle, right) −
Begin
nLeft := middle - left + 1
nRight := right - middle
define arrays leftArr and rightArr of size nLeft and nRight respectively
for i := 0 to nLeft-1 do
leftArr[i] := array[left + i]
done
for j := 0 to nRight-1 do
rightArr[j] := array[middle + j + 1]
done
i := 0, j := 0, k := left
while i < nLeft AND j < nRight do
if leftArr[i] <= rightArr[j] then
array[k] := leftArr[i]
i := i + 1
else
array[k] := rightArr[j]
j := j + 1
k := k + 1
done
while i < nLeft do
array[k] := leftArr[i]
i := i + 1
k := k + 1
done
while j < nRight do
array[k] := rightArr[j]
j := j + 1
k := k + 1
done
End위 의사코드의 흐름을 정리하면 다음과 같습니다.
1. 먼저 왼쪽 부분(left ~ middle)과 오른쪽 부분(middle+1 ~ right)의 크기를 계산하고, 각각의 임시 배열(leftArr, rightArr)에 데이터를 복사합니다.
2. 두 임시 배열의 앞부분부터 값을 비교하며, 더 작은 값을 원본 배열에 순서대로 채워 넣습니다.
3. 한쪽 배열이 모두 처리되면, 남은 배열의 요소들을 뒤에 이어 붙여 병합을 마무리합니다.
시간 및 공간 복잡도
병합 알고리즘은 두 리스트의 모든 요소를 한 번씩만 비교·이동하므로, 두 리스트의 길이를 각각 n, m이라 할 때 시간 복잡도는 O(n + m)입니다. 또한 병합 결과를 저장하기 위해 입력 크기만큼의 추가 배열이 필요하므로 공간 복잡도 역시 O(n + m)입니다. 이러한 안정적이고 예측 가능한 성능 덕분에 병합 알고리즘은 병합 정렬은 물론 외부 정렬(External Sort), 연결 리스트 병합 등 다양한 분야에서 널리 활용됩니다.