병합 정렬 (Merge Sort)

1. 개념 설명

(1) 병합 정렬은 분할 정복 방법으로 퀵 정렬처럼 배열을 두 부분으로 원소 개수가 0 또는 1이 될때까지

쪼개고 쪼개서 크기를 비교해 병합해 나간다.

 

(2) 병합 정렬은 합병 정렬이라고도 부른다.

 

(3) 병합 정렬은 대표적인 분할 정복 알고리즘으로 존 폰 노이만의 천재성을 엿볼 수 있는 알고리즘이다.

 

 

 

 

2. 과정

by wiki

 

- 실제로 수행되는 과정이며, 대표적인 분할 정복 방식이다.

 

by wiki

 

 

 

 

3. 코드

public class MergeSort {
    static int[] A = { 38, 27, 43, 9, 3, 82, 10 };
    static int[] tmp = new int[A.length];
 
    public static void main(String[] args) {
        System.out.println("정렬 전: " + Arrays.toString(A));
        mergeSort(0, A.length-1);
        System.out.println("정렬 후: " + Arrays.toString(A));
    }
    
    public static void mergeSort(int left, int right) {
        if(left>=right) return;
        
        int mid = (left+right)/2;
        mergeSort(left, mid);
        mergeSort(mid+1, right);
        
        int p = left;
        int q = mid+1;
        int idx = p;
        
        while(p<=mid || q<=right) {
            if(q>right || (p<=mid && A[p]<A[q])) {
                tmp[idx++] = A[p++];
            }else {
                tmp[idx++] = A[q++];
            }
        }
        for(int i=left; i<=right; i++) {
            A[i] = tmp[i];
        }
    }
}

 

 

 

 

4. 시간 복잡도

(1) 최선, 평균, 최악 모두 O(NlogN)의 시간 복잡도를 가진다.

 

 

 

 

5. 공간 복잡도

(1) 두 개의 배열을 병합할 때 병합 결과를 담아 놓을 배열이 추가로 필요하므, 공간 복잡도는 O(n)이다.

 

 

 

 

6. 장점

(1) 안정 정렬이다.

 

 

 

 

7. 단점

(1) 시간 복잡도가 같은 퀵정렬과는 성능이 전반적으로 뒤떨어진다.

 

(2) 입력 데이터 크기만한 메모리가 더 필요하다.

 

 

 

 

 

8. 퀵 정렬과 차이점

- 퀵 정렬: 우선 pivot을 통해 정렬 (partition) -> 영역을 쪼갬 (Quick Sort)

 

- 합병 정렬: 영역을 쪼갤 수 있을 만큼 쪼갬 (MergeSort) -> 정렬 (Merge)