개념
합병 정렬 또는 병합 정렬은 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다.
( * 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.)
구현(Java)
요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식
- mergeSort
public void mergeSort(int[] array, int left, int right) {
if(left < right) {
int mid = (left + right) / 2;
mergeSort(array, left, mid);
mergeSort(array, mid+1, right);
merge(array, left, mid, right);
}
}
- merge()
public static void merge(int[] array, int left, int mid, int right) {
int[] L = Arrays.copyOfRange(array, left, mid + 1);
int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
int i = 0, j = 0, k = left;
int ll = L.length, rl = R.length;
while(i < ll && j < rl) {
if(L[i] <= R[j]) {
array[k] = L[i++];
}
else {
array[k] = R[j++];
}
k++;
}
// remain
while(i < ll) {
array[k++] = L[i++];
}
while(j < rl) {
array[k++] = R[j++];
}
}
시간복잡도
최악의 경우(Worst cases) : T(n) = O(nlogn)
최선의 경우(Best cases) : T(n) = Ω(nlogn)
평균의 경우(Average cases) : T(n) = Θ(nlogn)
비교
퀵정렬 : 우선 피벗을 통해 정렬(partition) → 영역을 쪼갬(quickSort)
합병정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬(merge)
참고
'CS > 알고리즘' 카테고리의 다른 글
힙 정렬(Heap Sort) (0) | 2024.06.15 |
---|---|
기수 정렬(Radix sort) (0) | 2024.06.15 |
퀵 정렬(Quick Sort) (0) | 2024.06.13 |
거품 정렬(Bubble Sort) (0) | 2024.06.13 |
삽입 정렬(Insertion Sort) (1) | 2024.06.13 |