1. Merge Sort란 무엇일까?
주어진 배열을 작은 부분 배열로 나누고, 이들을 정렬한 후 다시 합치는 방식으로 동작합니다. 간단히 말해, 큰 문제를 작은 문제로 나누고 그 작은 문제들을 해결한 후 합쳐서 최종 결과를 얻는 방식입니다.
2. Merge Sort가 동작하는 방식
1. 분할 (Divide)
주어진 배열을 두 개의 작은 배열로 나눕니다. 이 과정을 배열의 크기가 1이 될 때까지 반복합니다. 배열의 크기가 1인 배열은 이미 정렬된 상태로 간주되기 때문에 더 이상 나누지 않습니다.
2. 정복 (Conquer)
나눠진 배열을 재귀적으로 정렬합니다. 즉, 작은 배열들을 정렬하여 정렬된 배열로 만들어냅니다.
3. 병합 (Merge)
정렬된 두 배열을 합쳐서 하나의 정렬된 배열을 만듭니다. 병합 과정에서는 두 배열의 값을 하나씩 비교하며, 더 작은 값을 새로운 배열에 넣는 방식으로 진행됩니다.
3. Merge Sort의 특징
- 시간 복잡도 : Merge Sort의 시간 복잡도는 O(n log n)입니다. 여기서
n은 배열의 크기입니다. 배열을 절반씩 나누는 과정에서log n이 발생하고, 각 분할된 배열을 합치는 과정에서n이 걸리므로 최종적으로O(n log n)의 시간이 걸립니다. - 공간 복잡도 : 병합을 위해 추가적인 배열을 사용해야 하므로 공간 복잡도는 O(n)입니다. 이 때문에 메모리 사용량이 다소 많을 수 있습니다.
- 안정성 : Merge Sort는 안정적인 정렬 알고리즘입니다. 즉, 두 값이 같을 때 원래의 배열 순서를 유지합니다. 예를 들어, 값이 같더라도 배열에서 왼쪽에 있던 값은 정렬 후에도 왼쪽에 남게 됩니다.
4. Merge Sort의 장점과 단점
장점
- 효율적인 정렬 : Merge Sort는 최악의 경우에도 O(n log n)이라는 일정한 시간 복잡도를 유지하기 때문에 큰 데이터에도 매우 효율적입니다.
- 안정적인 정렬 : 안정적인 정렬을 제공하기 때문에, 원본 배열의 순서를 그대로 유지하고 싶을 때 유용합니다.
단점
- 공간이 추가로 필요 : 병합 과정에서 배열을 추가로 만들기 때문에, O(n)의 추가 공간이 필요합니다. 따라서 메모리 사용이 많을 수 있습니다.
- 속도가 빠른 다른 알고리즘에 비해 느릴 수 있음 : 예를 들어, 작은 배열에 대해서는 Quick Sort나 Insertion Sort가 더 빠를 수 있습니다.
5. Merge Sort 구현 (Java)
import java.util.Arrays;
class Main {
public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10}; // 정렬할 배열
System.out.println("원본 배열 : "+Arrays.toString(arr));
mergeSort(arr);
System.out.println("정렬된 배열 : "+Arrays.toString(arr));
}
public static void mergeSort(int[] arr) {
if(arr.length < 2) {
return; // 배열의 크기가 1보다 작으면 이미 정렬된 상
}
int mid = arr.length / 2; // 배열의 중간 지점
int[] left = Arrays.copyOfRange(arr, 0, mid); // 왼쪽 부분 배열
int[] right = Arrays.copyOfRange(arr, mid, arr.length); // 오른쪽 부분 배열
mergeSort(left); // 왼쪽 배열 재귀적으로 정렬
mergeSort(right); // 오른쪽 배열 재귀적으로 정렬
merge(arr, left, right);
}
public static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while(i < left.length && j < right.length) {
if(left[i] < right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while(i < left.length) {
arr[k++] = left[i++];
}
while(j < right.length) {
arr[k++] = right[j++];
}
}
}6. Merge Sort 동작 과정
초기 배열 : [38, 27, 43, 3, 9, 82, 10]
1. 최초 분할 : [38, 27, 43](왼쪽), [3, 9, 82, 10](오른쪽)
왼쪽 [38, 27, 43] 분할과 병합
2. [38, 27, 43]을 [38](왼쪽), [27, 43] (오른쪽) 분할
3. [38] 크기가 1이므로 분할 종료
4. [27, 43]을 [27](왼쪽), [43](오른쪽) 분할
5. [27] 크기가 1이므로 분할 종료
6. [43] 크기가 1이므로 분할 종료
7. [27] 과 [43]을 병합 [27,43]
8. [38]과 [27, 43]을 병합 [27, 38, 43]
오른쪽 [3, 9, 82, 10] 분할과 병합
9. [3, 9, 82, 10]을 [3, 9](왼쪽), [82, 10](오른쪽) 분할
10. [3, 9]을 [3](왼쪽), [9](오른쪽) 분할
11. [3] 크기 1이므로 분할 종료
12. [9] 크기 1이므로 분할 종료
13. [3], [9] 병합 [3,9]
14. [82, 10]을 [82](왼쪽), [10](오른쪽) 분할
15. [82]크기 1이므로 분할 종료
16. [10]크기 1이므로 분할 종료
17. [82], [10] 병합 [10, 82]
18. [3, 9], [10, 82] 병합 [3, 9, 10, 82]
최종 병합
19. [27, 38, 43], [3, 9, 10, 82] 병합 [3, 9, 10, 27, 38, 43, 82]
