오늘은 병합 정렬에 대해 알아보자.
📘 병합 정렬
병합 정렬(merge sort)은 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘이다.
각 배열에서 선택한 요소의 값을 비교하여 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업을 반복하여 정렬을 마치는 배열을 만든다.
그림과 같이 a와 b의 배열을 병합하여 배열 c에 저장하여 배열을 완성하는 방법이다.
✏ 병합 정렬 코드
코드로 한번 알아보자.
// 정렬을 마친 배열 a, b를 병합하여 배열 c에 저장
static void merge(int[] a, int na, int[] b, int nb, int[] c) {
int pa = 0;
int pb = 0;
int pc = 0;
while (pa < na && pb < nb) // 작은 값을 저장
c[pc++] = (a[pa] <= b[pb]) ? a[pa++] : b[pb++];
while (pa < na) // a에 남아 있는 요소를 복사
c[pc++] = a[pa++];
while (pb < nb) // b에 남아 있는 요소를 복사
c[pc++] = b[pb++];
}위의 코드는 각각의 배열을 병합하며 정렬하는 코드이다.
na, nb는 각각 배열 a,b의 요소의 개수이고
pa, pb, pc는 각각 배열 a,b,c를 스캔할 때 선택할 요소의 인덱스이다.
while문을 이용하여 배열 a와 b의 각각 요소의 크기를 비교하여 배열 c에 저장하게 한다.
위처럼 정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬이라고 한다.
병합 정렬 알고리즘을 정리하면 다음과 같다.
배열의 요소 개수가 2개 이상인 경우
1. 배열의 앞부분을 병합 정렬로 정렬한다.
2. 배열의 뒷부분을 병합 정렬로 정렬한다.
3. 배열의 앞부분과 뒷부분을 병합한다.위의 알고리즘을 바탕으로 코드를 작성해보자.
static int[] buff; // 작업용 배열
// a[left] ~ a[right]를 재귀적으로 병합 정렬
static void mergeSort(int[] a, int left, int right) {
if (left < right) {
int i;
int center = (left + right) / 2;
int p = 0;
int j = 0;
int k = left;
mergeSort(a, left, center); // 배열의 앞부분을 병합 정렬
mergeSort(a, center + 1, right); // 배열의 뒷부분을 병합 정렬
for (i = left; i <= center; i++)
buff[p++] = a[i];
while (i <= right && j < p)
a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
while (j < p)
a[k++] = buff[j++];
}
}
// 병합 정렬
static void merge(int[] a, int n) {
buff = new int[n]; // 작업용 배열을 생성
mergeSort(a, 0, n - 1); // 배열 전체를 병합 정렬
buff = null; // 작업용 배열을 해제제
}
merge메서드는 병합한 결과를 일시적으로 저장할 배열인 buff를 생성한다.
그런 다음 실제로 정렬 작업을 수행할 mergeSort메서드를 호출한다.
mergeSort메서드는 a(정렬할 배열),left,right(첫 번째, 마지막 요소의 인덱스)를 인자로 전달 받으며 left가 right보다 작을 때 동작한다.
가장 먼저 앞부분(a[left] ~ a[center])과 뒷부분(a[center + 1] ~ a[right])에 대해서 mergeSort메서드를 재귀 호출한다.
✏ 병합 정렬 시간 복잡도
배열 병합의 시간 복잡도는 O(n)이고 데이터의 요소 개수가 n개일 때, 병합 정렬의 단계는 log n 만큼 필요하므로 전체 시간 복잡도는 O(n log n)이라고 할 수 있다.
또한 병합 정렬은 서로 떨어져 있는 요소를 교환하는 것이 아니므로 안정적인 정렬 방법이라고 할 수 있다.
