병합 정렬(Merge Sort)이란?
병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 기법을 활용하는 대표적인 정렬 알고리즘입니다. 배열을 두 부분으로 나눈 뒤, 각 부분에 대해 재귀적으로 자기 자신을 호출하며 이 과정을 배열이 완전히 정렬될 때까지 반복합니다.
병합 정렬의 시간 복잡도는 최악의 경우에도 O(n log n)으로 안정적인 성능을 보이며, 데이터가 이미 어느 정도 정렬되어 있거나 역순으로 배치된 경우에도 일관된 성능을 유지한다는 장점이 있습니다.
C# 병합 정렬 예제 코드
다음은 C#으로 병합 정렬을 구현한 전체 프로그램입니다.
using System;
namespace MergeSortDemo {
class Example {
static public void merge(int[] arr, int p, int q, int r) {
int i, j, k;
int n1 = q - p + 1;
int n2 = r - q;
int[] L = new int[n1];
int[] R = new int[n2];
for (i = 0; i < n1; i++) {
L[i] = arr[p + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[q + 1 + j];
}
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
static public void mergeSort(int[] arr, int p, int r) {
if (p < r) {
int q = (p + r) / 2;
mergeSort(arr, p, q);
mergeSort(arr, q + 1, r);
merge(arr, p, q, r);
}
}
static void Main(string[] args) {
int[] arr = {76, 89, 23, 1, 55, 78, 99, 12, 65, 100};
int n = 10, i;
Console.WriteLine("Merge Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
mergeSort(arr, 0, n-1);
Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
}
}
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
Merge Sort Initial array is: 76 89 23 1 55 78 99 12 65 100 Sorted Array is: 1 12 23 55 65 76 78 89 99 100
코드 상세 분석
1. Main() 함수 — 초기 배열 출력 및 정렬 호출
Main() 함수에서는 먼저 초기 배열을 화면에 출력합니다. 그런 다음 mergeSort() 함수를 호출하여 배열에 대한 병합 정렬을 수행합니다. 해당 코드는 다음과 같습니다.
int[] arr = {76, 89, 23, 1, 55, 78, 99, 12, 65, 100};
int n = 10, i;
Console.WriteLine("Merge Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
mergeSort(arr, 0, n-1);2. mergeSort() 함수 — 배열 분할
mergeSort() 함수에서는 변수 q를 배열의 중간 지점(midpoint)으로 계산합니다. 그 후 생성된 두 개의 하위 배열 각각에 대해 mergeSort()를 재귀적으로 호출하고, 마지막으로 merge()를 호출하여 분할된 하위 배열들을 하나로 병합합니다.
if (p < r) {
int q = (p + r) / 2;
mergeSort(arr, p, q);
mergeSort(arr, q + 1, r);
merge(arr, p, q, r);
}여기서 p < r 조건은 하위 배열에 요소가 두 개 이상 존재할 때만 분할을 계속하도록 하는 종료 조건입니다. 요소가 하나뿐인 배열은 이미 정렬된 상태로 간주됩니다.
3. merge() 함수 — 정렬된 배열 병합
merge() 함수에는 두 개의 정렬된 하위 배열이 전달됩니다. 이 함수는 두 하위 배열을 결과 배열 역시 정렬된 상태가 되도록 하나의 배열로 병합하는 핵심 역할을 담당합니다.
int i, j, k;
int n1 = q - p + 1;
int n2 = r - q;
int[] L = new int[n1];
int[] R = new int[n2];
for (i = 0; i < n1; i++) {
L[i] = arr[p + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[q + 1 + j];
}
i = 0;
j = 0;
k = p;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}merge() 함수의 동작 순서를 정리하면 다음과 같습니다.
① 임시 배열 생성: 왼쪽 하위 배열 L과 오른쪽 하위 배열 R을 각각 생성한 뒤 원본 배열의 값을 복사합니다.
② 두 배열 비교 병합: L과 R의 앞쪽 요소부터 차례로 비교하여 더 작은 값을 원본 배열에 배치합니다. <= 비교를 사용하므로 병합 정렬은 안정 정렬(stable sort)이 됩니다.
③ 남은 요소 처리: 한쪽 배열의 모든 요소가 처리된 후, 다른 쪽 배열에 남아 있는 요소들을 그대로 뒤에 복사합니다.
병합 정렬의 특징 정리
장점: 최악의 경우에도 O(n log n)의 시간 복잡도를 보장하며, 안정 정렬이므로 동일한 값의 상대적 순서가 유지됩니다. 연결 리스트 정렬에도 효율적으로 적용할 수 있습니다.
단점: 병합 과정에서 추가적인 임시 배열 공간이 필요하므로 공간 복잡도가 O(n)입니다. 따라서 메모리가 제한적인 환경에서는 퀵 정렬(Quick Sort)과 같은 제자리 정렬 알고리즘이 더 적합할 수 있습니다.