#include <iostream>
using namespace std;
#define number 8
int sorted[8]; // 정렬된 배열. 반드시 전역 변수로 선언.
void merge(int a[], int m, int middle, int n){
// m: 정렬할 배열의 시작 지점
// middle: 정렬할 배열의 중간 지점
// n: 정렬할 배열의 끝 지점
int i = m;
int j = middle+1;
int k = m;
// 작은 순서대로 배열에 삽입
while(i<=middle && j <= n){
// i가 j보다 더 작으면 새로운 배열에 저장
if(a[i] <= a[j]){
sorted[k] = a[i];
i++;
}
// 그렇지 않으면 j 값 저장
else{
sorted[k] = a[j];
j++;
}
k++; // 한 번 저장하면 k 증가
}
// 남은 데이터 삽입
// i가 먼저 끝났다면 j 모두 새로운 배열에 저장
if(i > middle){
for(int t = j; t <= n; t++){
sorted[k] = a[t];
k++;
}
}
// j가 먼저 끝났으면 i 모두 새로운 배열에 저장
else{
for(int t = i;t<=middle;t++){
sorted[k] = a[t];
k++;
}
}
// 정렬된 배열을 실제 배열에 삽입
for(int t = m; t <= n; t++){
a[t] = sorted[t];
}
}
void merge_sort(int a[], int m, int n){
// 크기가 1보다 큰 경우 return
if(m < n){
int middle = (m+n) / 2;
merge_sort(a, m, middle); // middle을 기준으로 왼쪽 병합정렬
merge_sort(a, middle+1, n); // middle을 기준으로 오른쪽 병합정렬
merge(a, m, middle, n); // 정렬 후 합치기
}
}
int main(void){
int arr[number] = {7, 6, 5, 8, 3, 5, 9, 1};
merge_sort(arr, 0, number-1);
for(int i=0;i<number;i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
출력
1 3 5 5 6 7 8 9
시간 복잡도
병합정렬은 정확히 반씩 나눈다는 점에서 최악의 경우에도 NlogN을 보장한다.
☞ 퀵 정렬이 가지는 한계(Pivot 값에 따라 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(N^2)의 시간 복잡도를 가짐)를 보완할 수 있음.