병합 정렬(Merge Sort)이란?
병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 기법에 기반한 대표적인 정렬 알고리즘입니다. 시간 복잡도는 O(n log n)으로, 입력 데이터가 많아지더라도 비교적 안정적인 성능을 유지할 수 있으며, 최악의 경우에도 동일한 복잡도를 보장한다는 장점이 있습니다.
알고리즘의 기본 동작 과정은 다음과 같습니다. 먼저 배열을 동일한 크기의 두 부분으로 분할한 뒤, 각 부분을 정렬하고, 마지막으로 두 부분을 하나의 정렬된 배열로 병합합니다.
반복 병합 정렬(Iterative Merge Sort)의 동작 원리
반복 병합 정렬에서는 재귀 호출을 활용해 배열을 계속 절반씩 나누는 방식으로 분할 단계를 수행하고, 분할된 부분 배열들을 차례대로 병합하여 최종적으로 하나의 정렬된 배열을 완성합니다.
C 언어로 구현한 반복 병합 정렬 코드
다음은 C 언어로 작성한 병합 정렬의 전체 소스 코드입니다.
예제 코드
#include<stdlib.h>
#include<stdio.h>
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
i = 0, j = 0, k = l;
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++;
}
}
void iterativeMergeSort(int arr[], int l, int r) {
if (l < r){
int mid = l+(r-l)/2;
iterativeMergeSort(arr, l, mid);
iterativeMergeSort(arr, mid+1, r);
merge(arr, l, mid, r);
}
}
int main(){
int arr[] = {12, 11, 13, 5, 6, 7};
int size = sizeof(arr)/sizeof(arr[0]);
printf("\t\t ITERATIVE MERGE SORT \n");
printf("Unsorted Array : \t");
for (int i=0; i < size; i++)
printf("%d ",arr[i]);
iterativeMergeSort(arr, 0, size - 1);
printf("\nSorted array : \t");
for (int i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}코드 설명
- merge() 함수: 인덱스 l~m과 m+1~r에 해당하는 두 개의 정렬된 부분 배열을 임시 배열 L과 R에 복사한 뒤, 두 배열의 요소를 앞에서부터 비교하여 작은 값부터 원래 배열에 채워 넣습니다. 한쪽 배열이 모두 소진되면 남은 요소들을 그대로 뒤에 이어 붙여 하나의 정렬된 배열을 완성합니다.
- iterativeMergeSort() 함수: 배열의 중간 지점(mid)을 계산해 왼쪽 절반과 오른쪽 절반으로 나눈 후, 각각에 대해 자기 자신을 재귀적으로 호출하며 분할을 반복하고, 마지막에 merge() 함수를 호출해 두 부분을 하나로 병합합니다.
- main() 함수: 예제 배열 {12, 11, 13, 5, 6, 7}을 선언하고, 정렬되기 전 배열을 출력한 뒤 iterativeMergeSort()를 호출해 정렬을 수행하고 그 결과를 화면에 출력합니다.
실행 결과
ITERATIVE MERGE SORT Unsorted Array : 12 11 13 5 6 7 Sorted array : 5 6 7 11 12 13