Merge Sort 란?
기본적으로 병합정렬은 문제를 분할하고, 분할한 문제를 정복하여 합치는 과정이다.
병합 정렬은 기본적으로 분할 정복(Divide and Conquer) 알고리즘을 기반으로 정렬되는 방식이다.
병합 정렬에 대해 간단하게 말하면
정렬해야 할 리스트가 주어지면 해당 리스트를 분할을 반복하여 최대한 작게 쪼개진 시점에 부분 리스트에서 인접한 원소들끼리 비교하여 정렬하는 방식이다.
병합 정렬은 데이터를 비교하면서 찾기 때문에 비교 정렬이며, 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하기 때문에 제자리 정렬(in-place sort)가 아니다.
정확히는 제자리 정렬로 구현할 수는 있지만 그 대신 성능을 일부 포기해야 하며 매우 신중하게 구현되어야 한다.
병합 정렬의 구조상 최대한 작게 문제를 쪼개어 앞의 부분 리스트부터 차례대로 합쳐나가기 때문에 안정 정렬(Stable Sort) 알고리즘이기도 하다.
Merge Sort 방법
병합 정렬 과정
- 주어진 리스트를 절반으로 분할하여 부분 리스트로 나눈다. (Divide : 분할)
- 해당 부분 리스트의 길이가 1이 아니라면 1번 과정을 되풀이 한다.
- 인접한 부분 리스트끼리 정렬하여 합친다. (Conquer : 정복, Combine : 결합)
분할(Divide) : 리스트를 두 개의 리스트로 분할한다. 정복(Donquer) : 분할된 리스트를 정렬한다.
결합(Combine) : 정렬된 두 개의 리스트를 하나의 정렬된 리스트로 결합한다.
정렬 되는 과정을 아래와 같이 이미지로 확인하자.
주의할 점은 병합 정렬의 구현이 반드시 2개의 부분 리스트로 나누어야 한다는 점은 아니다.
어디까지나 가장 일반적으로 구현되는 방식이 절반으로 나누는 방식일 뿐이다.
보통 위 이미지와 같이 두 개의 부분 리스트로 나누는 방식을 two-way 방식이라고 한다.
일단 각각의 부분 리스트는 정렬된 상태라는 점을 이해하고 있어야 한다.
두 부분 리스트를 합쳐서 정렬할 때 굳이 삽입, 버블 정렬 등을 활용할 필요가 없다는 것이다.
따라서 아래 이미지와 같이 각 부분 리스트의 첫 번째 원소부터 순차적으로 비교만 해주면 된다.
이미 각각의 부분 리스트는 오름차순으로 정렬되어 있기 때문에 앞부분부터 시작하여 하나씩 비교해주며 정렬해주면 된다.
Merge Sort 흐름 예시
Merge Sort 구현
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] numArr = {8, 2, 6, 4, 7, 3, 9, 5};
mergeSort(numArr);
System.out.println(Arrays.toString(numArr));
}
private static void mergeSort(int[] numArr) {
int[] temp = new int[numArr.length];
sort(numArr, temp, 0, numArr.length - 1);
}
private static void sort(int[] numArr, int[] temp, int leftIdx, int rightIdx) {
if(leftIdx < rightIdx) {
int midIdx = (leftIdx + rightIdx) / 2;
sort(numArr, temp, leftIdx, midIdx);
sort(numArr, temp, midIdx + 1, rightIdx);
merge(numArr, temp, leftIdx, midIdx, rightIdx);
}
}
private static void merge(int[] numArr, int[] temp, int leftIdx, int midIdx, int rightIdx) {
int p = leftIdx;
int q = midIdx + 1;
int tempIdx = leftIdx;
while(p <= midIdx && q <= rightIdx) {
if(numArr[p] < numArr[q]) temp[tempIdx++] = numArr[p++];
else temp[tempIdx++] = numArr[q++];
}
while(p <= midIdx) temp[tempIdx++] = numArr[p++];
while(q <= rightIdx) temp[tempIdx++] = numArr[q++];
// for(int i = leftIdx; i <= rightIdx; i++) numArr[i] = temp[i];
System.arraycopy(temp, leftIdx, numArr, leftIdx, rightIdx - leftIdx + 1);
}
}
System.arraycopy()
배열의 복사하기 위해서 아래와 같이 for문을 사용하여 배열을 복사했었다.
for(int i = leftIdx; i <= rightIdx; i++) numArr[i] = temp[i];위 코드는 원래 배열의 값을 모두 복제해 또 하나의 배열을 생성하는 과정에서 자원이 낭비되고, 원래 배열과 복사본 배열의 자료형이 같아야 한다는 제약도 있다.
이를 해결하기 위해 "System" 클래스에 배열을 복사하는 "arraycopy" 메서드를 아래와 같이 사용한다.
System.arraycopy(src, srcPos, dest, destPos, length);
/*
src - 원래 배열
srcPos - 원래 배열의 복사 시작 위치
dest - 복사할 배열
destPost - 복사할 배열의 복사 시작 위치
length - 복사할 요소의 개수
*/System.arraycopy()를 사용함으로써 원하는 부분만 복사할 수 있고, 불필요한 인스턴스 생성을 방지하여 메모리 자원 낭비를 예방하며, 더 빠른 실행을 할 수 있다. 또한, 가독성 측면에서도 효율적이다.
Merge Sort 시간 복잡도
병합 정렬의 시간 복잡도는 n개의 데이터를 가지고 logN단계를 거치기 때문에 O(NlogN)이 된다.
퀵 정렬은 피봇을 어떻게 선택하느냐에 따라 최악의 시간 복잡도가 O(N^2)가 되지만, 병합 정렬은 항상 리스트를 절반으로 나누기 때문에 O(NlogN)의 시간 복잡도를 보장한다.
Merge Sort 장단점
장점
- 퀵 정렬은 데이터의 분포에 따라 최악의 경우 O(N^2)의 시간 복잡도를 갖는데 병합 정렬은 O(NlogN)의 시간 복잡도를 보장한다.
- 선택 정렬, 삽입 정렬같이 O(N^2)의 시간 복잡도를 가지고 있는 정렬 알고리즘보다 더 효율적이다.
단점
- 데이터가 배열로 구성된 경우 임시 배열이 필요하므로 추가 공간이 필요하다.
추가 공간을 사용하므로 제자리 정렬이 아니다. - 데이터의 크기가 큰 경우 이동 횟수가 많으므로 시간 낭비 발생
References
- Merge Sort
- System.arraycopy()
