Algorithm - Merge Sort (병합 정렬)

Merge Sort :

Divide and Conquer의 방식을 사용한 알고리즘. 문제를 작은 2개의 문제로 분리하고 각각을 해결한 후, 그 결과물들을 모아서 원래의 문제를 해결하는 전략. 순환 호출을 주로 사용해서 구현. (과정 : 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 봄 - 그렇지 않다면 정렬되지 않은 리스트를 반으로 잘라서 비슷한 크기의 리스트 두개로 나눔[divide]. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬[conquer]. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병[merge]) / Quick sort와 동일한 시간 복잡도인 O(N*LogN). Quick sort는 pivot값에 따라 편향되게 분할될 수 있으므로 최악의 경우 O(N^2)의 시간 복잡도를 가질 수 있지만 Merge sort는 정확히 반씩 나누기 때문에 최악의 경우에도 O(N*LogN)을 보장함. / 

 

Merge sort 과정 :

- 초기 상태의 List 하나를 두 개의 List가 되도록 분할해 나가면서, 최종적으로 길이가 1이 될 때까지 분할. (ex. 초기 List가 {6 3 5 1 8 2 7 4} 라면 {6} {3} {5} {1} {8} {2} {7} {4} 로 분할). -> 6과 3을 가져온 후 오름차순 정렬하여 하나의 리스트에 병합 -> {3, 6} -> 5, 1도 {1, 5}가 되고 나머지도 {2, 8} {4, 7}로 size가 2인 부분 list가 됨. -> size 2의 부분 list들을 size 4의 부분 list가 되도록 정렬하면서 병합. -> {3, 6}과 {1, 5} 를 정렬, 병합하면 {1, 3, 5, 6}이 됨. (① 3과 1을 비교, 1이 더 작으므로 1이 결과 list에 먼저 들어감. ② 3과 5를 비교, 3이 더 작으므로 다음으로 들어감. ③ 6과 5 비교 후 정렬.) -> {2, 8} {4, 7} 정렬, 병합하면 {2, 4, 7, 8} (①2와 4비교, 2가 list에 박힘. ② 8과 4비교, 4가 list에 박힘. ③ 8, 7 비교, 7이 박힘.) ==> 왼쪽과 오른쪽 list의 element들을 하나씩 비교하면서 더 작은 값을 결과 list에 박으면 됨. -> size 4짜리 부분 list들을 size 8의 list로 만들기 위해 마찬가지로 정렬, 병합 반복. 

 

Merge sort 특징 :

합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 list를 합병(merge)하는 단계.

[Array] 정렬할 자료를 배열로 구성한다면, 임시로 결과를 저장하는 배열이 따로 필요하기 때문에 메모리 자원낭비로 비효율적일수 있음. 제자리 정렬(in-place sorting)이 아님. List의 크기가 큰 경우에는 이동 횟수가 많으므로 시간이 오래 걸릴 수 있음. 정렬 방법이 안정적임 - 데이터가 분포해 있는 상황의 영향을 적게 받음, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일함. / [Linked LIst] 정렬할 자료를 Linked List로 구성한다면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아짐. 제자리 정렬로 구현됨. 따라서 크기가 큰 레코드를 정렬할 경우에 Linked List를 사용한다면, Merge sort는 다른 정렬들에 비교해서 가장 효율적임.

 

public class MergeSort {
	static int MAX_SIZE = 8;
    static int SORTED[MAX_SIZE];

	public static void merge(int list[], int left, int mid, int right) {
    	int i, j, k, l;
        i = left;
        j = mid + 1;
        k = left;
        
        while (i <= mid && j <= right) {
        	if (list[i] <= list[j]) {
            	SORTED[k++] = list[i++];
            } else {
            	SORTED[k++] = list[j++];
            }
        }
        
        if (i > mid) { // 남은 값들 일괄 복사
        	for (l = j; l <= right; l++) {
            	SORTED[k++] = list[l];
            }
        } else {
        	for (l = i; l <= mid; l++) {
            	SORTED[k++] = list[l];
            }
        }
        
        for (l = left; l <= right; l++) { // 수행했던 값 리스트를 list로 다시 복사
        	list[l] = SORTED[l];
        }
    }

	public static void merge_sort(int list[], int left, int right) {
    	int mid;
        
        if (left < right) {
        	mid = (left + right) / 2; // 중간 위치 계산, list 분할.
            merge_sort(list, left, mid); // 앞쪽 부분 list 정렬
            merge_sort(list, mid+1, right); // 뒤쪽 부분 list 정렬
            merge(list, left, mid, right); // 정렬된 2개의 부분 배열 합병
        }
    }

	public static void main(String[] args) {
    	int n = MAX_SIZE;
        int list[n] = {6, 3, 5, 1, 8, 2, 7, 4};
        
        merge_sort(list, 0, n-1);
        
        for (int i = 0; i < n; i++) {
        	System.out.println(list[i]);
        }
    }
}