병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 기법에 기반한 대표적인 정렬 알고리즘입니다. 전체 데이터 집합을 더 작은 단위로 나눈 뒤, 각 부분을 정렬된 순서로 다시 합쳐(merge) 하나의 정렬된 배열을 만듭니다. 특히 최악의 경우에도 O(n log n)의 낮은 시간 복잡도를 유지하기 때문에 성능이 중요한 상황에서 매우 효과적입니다.
병합 정렬의 시간·공간 복잡도
- 시간 복잡도: 모든 경우(최선·평균·최악)에서 O(n log n)
- 공간 복잡도: O(n) — 병합 과정에서 임시 배열이 필요합니다.
입력 및 출력 예시
입력:
정렬되지 않은 리스트: 14 20 78 98 20 45
출력:
정렬 전 배열: 14 20 78 98 20 45
정렬 후 배열: 14 20 20 45 78 98
알고리즘
merge(array, left, middle, right)
입력 − 데이터 배열, left(왼쪽 인덱스), middle(중간 인덱스), right(오른쪽 인덱스)
출력 − 두 부분 배열이 병합된 리스트
Begin
nLeft := m - left + 1
nRight := right - m
크기가 nLeft, nRight인 배열 leftArr와 rightArr 선언
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)
입력 − 데이터 배열과 배열의 하한(left), 상한(right) 인덱스
출력 − 정렬된 배열
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
C++ 구현 예제
#include<iostream>
using namespace std;
void swapping(int &a, int &b) { // a와 b의 값을 교환
int temp;
temp = a;
a = b;
b = temp;
}
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[nl], rarr[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++;
}
}
void mergeSort(int *array, int l, int r) {
int m;
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[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);
}
실행 결과
요소의 개수를 입력하세요: 6
요소를 입력하세요:
14 20 78 98 20 45
정렬 전 배열: 14 20 78 98 20 45
정렬 후 배열: 14 20 20 45 78 98
정리
병합 정렬은 데이터를 반으로 나누어 재귀적으로 정렬한 뒤 병합하는 방식으로 동작하며, 어떤 입력이 들어와도 안정적으로 O(n log n)의 성능을 보장합니다. 다만 병합 과정에서 추가 메모리(O(n))가 필요하다는 점을 기억해야 합니다. 연결 리스트 정렬이나 외부 정렬(대용량 파일 정렬) 등 안정성과 일관된 성능이 필요한 분야에서 널리 활용됩니다.