병합 정렬(Merge Sort)이란?
병합 정렬은 분할 정복(Divide and Conquer) 기법에 기반한 대표적인 정렬 알고리즘입니다. 전체 데이터 집합을 더 작은 단위로 나누고(분할), 각 부분을 정렬한 뒤(정복), 정렬된 순서대로 다시 합쳐서(결합) 하나의 정렬된 배열을 만드는 방식으로 동작합니다.
병합 정렬의 가장 큰 장점은 최악의 경우에도 O(n log n)의 시간 복잡도를 보장한다는 점입니다. 따라서 데이터가 이미 역순으로 정렬되어 있는 등 불리한 상황에서도 퀵 정렬보다 안정적인 성능을 발휘합니다.
병합 정렬의 복잡도
시간 복잡도: 최선·평균·최악의 모든 경우에서 O(n log n)
공간 복잡도: O(n)
안정성: 같은 값을 가진 요소의 상대적 순서가 유지되는 안정 정렬(stable sort)
예제 입출력
입력(정렬되지 않은 리스트): 14 20 78 98 20 45 출력(정렬 후 배열): 14 20 20 45 78 98
알고리즘
병합 정렬은 두 개의 핵심 함수로 구성됩니다. 정렬된 두 구간을 하나로 합치는 merge() 함수와, 배열을 재귀적으로 반으로 나누는 mergeSort() 함수입니다.
merge(array, left, middle, right)
입력: 데이터 배열, 왼쪽(left)·중간(middle)·오른쪽(right) 인덱스
출력: 두 구간이 병합된 리스트
Begin
nLeft := m - left + 1
nRight := right - m
leftArr와 rightArr 배열을 각각 nLeft, nRight 크기로 선언
for i := 0 to nLeft do
leftArr[i] := array[left + i]
done
for j := 0 to nRight 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
두 임시 배열의 요소를 앞에서부터 비교하여 작은 값부터 원래 배열에 채워 넣고, 한쪽 배열이 먼저 소진되면 남은 요소들을 그대로 뒤에 붙여 넣는 것이 핵심입니다.
mergeSort(array, left, right)
입력: 데이터 배열과 배열의 하한(lower bound)·상한(upper bound) 인덱스
출력: 정렬된 배열
Begin
if lower < right then
mid := left + (right - left) / 2
mergeSort(array, left, mid)
mergeSort(array, mid + 1, right)
merge(array, left, mid, right)
End
배열을 중간 지점을 기준으로 계속 반씩 나누다가, 요소가 하나만 남으면 재귀 호출을 종료하고 돌아오는 경로에서 merge()를 통해 정렬하며 병합합니다.
C++ 예제 코드
다음은 위 알고리즘을 C++로 구현한 전체 코드입니다. 사용자로부터 요소의 개수와 값을 입력받은 뒤, 정렬 전후의 배열을 화면에 출력합니다. 동적 할당을 활용해 표준 C++ 규격에서도 문제없이 동작하도록 작성했습니다.
#include <iostream>
using namespace std;
void display(int *array, int size) {
for(int i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
void merge(int *array, int l, int m, int r) {
int i, j, k, nl, nr;
// 왼쪽, 오른쪽 하위 배열의 크기 계산
nl = m - l + 1;
nr = r - m;
int *larr = new int[nl];
int *rarr = new int[nr];
// 임시 배열 채우기
for(i = 0; i < nl; i++)
larr[i] = array[l + i];
for(j = 0; j < nr; j++)
rarr[j] = array[m + 1 + j];
i = 0; j = 0; k = l;
// 임시 배열을 원래 배열로 병합
while(i < nl && j < nr) {
if(larr[i] <= rarr[j]) {
array[k] = larr[i];
i++;
} else {
array[k] = rarr[j];
j++;
}
k++;
}
while(i < nl) { // 왼쪽 배열에 남은 요소 복사
array[k] = larr[i];
i++; k++;
}
while(j < nr) { // 오른쪽 배열에 남은 요소 복사
array[k] = rarr[j];
j++; k++;
}
delete[] larr;
delete[] rarr;
}
void mergeSort(int *array, int l, int r) {
if(l < r) {
int m = l + (r - l) / 2;
// 앞쪽 절반과 뒤쪽 절반을 각각 재귀적으로 정렬
mergeSort(array, l, m);
mergeSort(array, m + 1, r);
merge(array, l, m, r);
}
}
int main() {
int n;
cout << "요소 개수 입력: ";
cin >> n;
int *arr = new int[n]; // 입력받은 크기만큼 배열 생성
cout << "요소 입력:" << endl;
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "정렬 전 배열: ";
display(arr, n);
mergeSort(arr, 0, n - 1); // 마지막 인덱스는 (n-1)
cout << "정렬 후 배열: ";
display(arr, n);
delete[] arr;
return 0;
}
실행 결과
요소 개수 입력: 6 요소 입력: 14 20 78 98 20 45 정렬 전 배열: 14 20 78 98 20 45 정렬 후 배열: 14 20 20 45 78 98
마무리: 병합 정렬은 언제 사용할까?
병합 정렬은 입력 데이터의 초기 상태와 관계없이 항상 O(n log n)의 성능을 보장하고, 안정 정렬이라는 특성 덕분에 연결 리스트 정렬이나 디스크에 있는 대용량 데이터를 다루는 외부 정렬(external sort) 등에 널리 활용됩니다. 다만 병합 과정에서 추가 메모리 O(n)이 필요하다는 점이 퀵 정렬 대비 단점이므로, 메모리 여유와 안정성 요구 사항을 고려해 선택하는 것이 좋습니다.