병합 정렬 알고리즘(Merge Sort)
병합 정렬은 데이터 배열을 정확히 반으로 나누고 나중에 합쳐서 정렬하는 방식입니다. 정확하게 5:5로 나누기때문에 피벗(Pivot)이 존재하지 않습니다.
8 2 6 5 1 4 2 7
위와 같은 수가 있을 때 수들을 오름차순하는 병합 정렬을 해보겠습니다.
8개의 데이터를 나눌 수 없을때까지 반으로 나누면 크기가 1인 배열로 나누어집니다.
8 | 2 | 6 | 5 | 1 | 4 | 2 | 7
나누는 과정이 끝났다면 이제 데이터를 2의 배수만큼 합치고 합치는 순간 각각을 정렬합니다.
1차 합 : 2 8 | 5 6 | 1 4 | 2 7
2차 합 : 2 5 6 8 | 1 2 4 7
3차 합 : 1 2 2 4 5 6 7 8
알고리즘 구현
// Algorithm Analysis
// 병합 정렬 (Merge Sort) : 데이터 배열을 정확히 반으로 나누고 나중에 합쳐서 정렬.
#include <stdio.h>
int num = 8;
int sorted[8]; // 정렬된 배열은 반드시 전역으로.
void merge(int a[], int m, int mid, int n) { // m:시작점, mid:중간점, n:끝점
int i = m;
int j = mid + 1;
int k = m;
// 작은 순서대로 배열에 삽입
while (i <= mid && j <= n) {
if (a[i] <= a[j]) {
sorted[k] = a[i];
i++;
}
else {
sorted[k] = a[j];
j++;
}
k++;
}
// 남은 데이터 삽입
if (i > mid) {
for (int p = j; p <= n; p++) {
sorted[k] = a[p];
k++;
}
}
else {
for (int p = i; p <= mid; p++) {
sorted[k] = a[p];
k++;
}
}
// 정렬된 배열을 삽입
for (int p = m; p <= n; p++) {
a[p] = sorted[p];
}
}
void mergeSort(int a[], int m, int n) { // 배열 나누는 과정
// 크기가 1보다 큰 경우
if (m < n) {
int mid = (m + n) / 2;
mergeSort(a, m, mid);
mergeSort(a, mid + 1, n);
merge(a, m, mid, n);
}
}
int main() {
int arr[8] = { 8, 2, 6, 5, 1, 4, 2, 7 };
mergeSort(arr, 0, num - 1);
for (int i = 0; i < num; i++) {
printf("%d ", arr[i]);
}
return 0;
}
시간 복잡도 : O(N * logN)
퀵 정렬보다 더 빠르다고 할 수는 없지만 데이터를 정확히 반으로 나누고 정렬하기에 항상 O(N * logN)의 시간 복잡도를 유지하므로 퀵 정렬의 한계점을 보완할 수 있는 알고리즘입니다.
* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.