[알고리즘-이론] 병합 정렬(Merge Sort)

---

병합 정렬(Merge Sort)란?

 

병합정렬은 앞서 설명한 선택 정렬, 버블 정렬, 삽입 정렬과는 비교 할 수 없는 시간 복잡도인 O(n log n)의 알고리즘이다.

 

현대의 컴퓨터 개념의 시초가 되었떤 폰 노이만(John von Neumann)이 제안한 방법으로 분할 정복 알고리즘중 하나이다.

재귀 호출을 사용하여 정렬의 효율을 극대화 시켰다.

 

과정

• 정렬되지 않은 배열을 절반으로 잘라 비슷한 크기의 두 부분의 배열으로 나눈다.

• 각 부분 배열의 크기가 0이 될 때 까지 반복하고 0이 되면 각 부분을 재귀적으로 합치는 과정을 수행한다.

• 합치는 과정이 수행될 때 실질적 정렬이 이루어진다.

이런식으로 진행하면 단계를 세 단계로 나눌 수 있다.

 

1. 분할 : 입력 배열을 같은 크기의 2 개의 부분 배열로 분할한다.

2. 정복 : 부분 배열을 정리한다. 부분 배열의 크기가 충분히 작지 않으면 재귀 호출을 이용해 다시 분할 시퀀스를 시작한다.

3. 결합 : 정렬된 부분 배열을 하나의 배열에 결합시킨다.

pseudo code

mergeSort(A[], p, r){
    if(p<r) then {                        .... 1
        q <- (p+r) / 2;                    .... 2
        mergeSort(A, p, q);              .... 3
        mergeSort(A, q+1, r);            .... 4
        merge(A, p, q, r);                .... 5
    }
}

merge(A[], p, q, r){                    .... 6
    정렬되어 있는 두 배열 A[p...q] 와 A[q+1...r]을 합쳐         .... 7
    정렬된 하나의 배열 A[p...r]을 만든다.                    .... 8
}

 

이중 merge를 좀 더 구체적으로 기술 하면 다음과 같다.

 

// A[p...q]와 A[q+1...r]을 병합해서 A[p...r]을 정렬된 상태로 만든다.
// A[p...q]와 A[q+1...r]은 이미 정렬되어 있다.
merge{
    i <- p; j <- q+1; t <- 1;
    while(i<=1 and j<= r){
        if(A[i] <= A[j])
        then tmp[t++] <- A[i++];
        else tmp[t++] <- A[j++];
    }
    while(i <= q)
        tmp[t++] <- A[i++];
    while(j <= r)
        tmp[t++] <- A[j++];
    i <- p; t <- 1;
    while(i <= r)
        A[i++] <- tmp[t++];
}

- ....2 : 먼저 배열의 중앙 부분을 찾기 위해 .... 2 처럼 배열의 중앙 q를 찾는다.

- ....3 : A[1...q] 까지 배열에 또 mergeSort를 호출한다.

- ....4 : A[q+1 ... r] 까지 배열에 또 mergeSort를 호출한다.

- ....5 : 분할했던 모든 배열을 합친다. 이 과정에서 정렬이 이루어진다.

---

병합 정렬(Merge Sort)의 자바 코드