병합정렬
- 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식
- 분할 정복 알고리즘 활용
1) 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냄
2) top-down 방식
3) 안정 정렬
- 시간 복잡도 : O(n log n)
병합 정렬 과정
- 분할 단계: 전체 자료 집합에 대하여, 최소 크기의 부분집합이 될 때까지 분할 작업을 계속한다. 👉 mergeSort( )
- 병합 단계: 2개의 부분 집합을 정렬하면서 하나의 집합으로 병합
(8개의 부분집합이 1개로 병합될 때까지 반복함) 👉 merge( )
병합 정렬 구현
import java.util.Arrays;
public class MergeSort {
static int[] sortedArr;
public static void main(String[] args) {
int[] arr = { 77, 32, 37, 17, 22, 8, 13, 42 };
sortedArr = new int[arr.length];
System.out.println("정렬전: " + Arrays.toString(arr));
mergeSort(arr, 0, arr.length-1);
System.out.println("정렬후: " + Arrays.toString(arr));
}
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int L = left;
int R = mid + 1;
int idx = left;
while (L <= mid && R <= right) {
if (arr[L] <= arr[R])
sortedArr[idx++] = arr[L++];
else
sortedArr[idx++] = arr[R++];
}
if (L <= mid) {
for (int i = L; i <= mid; i++)
sortedArr[idx++] = arr[i];
}
else {
for (int i = R; i <= right; i++)
sortedArr[idx++] = arr[i];
}
for (int i = left; i <= right; i++)
arr[i] = sortedArr[i];
}
}