[Algorithms] Merge Sort | 병합 정렬

Merge Sort

 

병합 정렬

 

 

 

- Divide and Conquer 알고리즘 중 하나로, 정렬된 배열을 합쳐가며 정렬하는 알고리즘이다.

- Time Complexity : 최악의 경우 \(\Theta(n\log n)\)

 

 

* Comparison Sort Algorithms (비교 정렬 알고리즘)

• Selection Sort (선택 정렬) (URL)
• Bubble Sort (버블 정렬) (URL)
• Insertion Sort (삽입 정렬) (URL)
• Merge Sort (병합 정렬) (URL)
• Quick Sort (퀵 정렬) (URL)
• Heap Sort (힙 정렬) (URL)

---

Mechanism (메커니즘)

- 배열 \(\texttt{A[1 ... n]}\)*을 재귀를 통해 요소가 하나가 될 때 까지 계속해서 절반씩 나눈 후, 나눠진 각각의 원소들을 대소 관계를 비교하며 정렬 및 병합해 나아간다.

 

* \(\texttt{A[1 ... n]}\) : 배열 \(\texttt{A[1]}, \cdots,\texttt{ A[n]}\)을 간략히 표현한 표기법이다.

 

---

Pseudo Code (의사 코드)

mergeSort(A[], p, r) {
    if (p < r) then {
        q ← Chopping((p + r) / 2);    // p, r의 중간 지점 계산
        mergeSort(A, p, q);           // 전반부 나누기
        mergeSort(A, q + 1, r);       // 후반부 나누기
        merge(A, p, q, r);            // 병합
    }
}


merge(A[], p, q, r) {
// A[p...q]와 A[q+1...r]을 대소관계를 고려해가며 병합해 A[p...r]을 정렬된 상태로 만든다.
// A[p...q]와 A[q+1...r]는 이미 정렬이 완료되어 있는 상태이다.

    i ← p;
    j ← q + 1;
    t ← 1;
    
    while (i ≤ q 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[]에 저장
        A[i++] ← tmp[t++];
}
    

 

---

Performance Evaluation (알고리즘 성능 평가)

 

병합 정렬의 수행 시간은 최악의 경우에 \(\Theta(n\log n)\) 이다.

pf) \(T(n)\)은 크기가 \(n\)인 배열을 정렬하는 데 필요한 시간이라고 하자.
\(a\)는 크기가 1인 문제를 푸는데 걸리는 시간,
\(c\)는 병합에 드는 시간을 충분히 잡아주기 위해 \(n\)에 곱해지는 상수일 때,

\(T(n) \leq \begin{cases}a & \mbox{if } n = 1 \\2T({n \over 2}) + cn & \mbox{if } n > 1\end{cases}\)
으로 나타낼 수 있다.
여기서 비교의 횟수만으로 수행 시간을 분석한다면 \(c = 1\)로 놓아도 무방하다.
위의 부등식을 \(n = 2^k\)*라 두고 풀었을 때 결과는 아래와 같다.
\(T(n) \leq 2T({n \over 2}) + cn \\\qquad \ \leq 2(2T({n \over 4}) + c{n \over 2}) + cn = 2^{2}T({n \over 2^{2}}) + 2cn \\\qquad \ \leq 2^{2}(2T({n \over 2^{3}}) + c{n \over 2^{2}}) + 2cn = 2^{3}T({n \over 2^{3}}) + 3cn \\ \\ \qquad \ \cdots \\ \\\qquad \ \leq 2^{k}T({n \over 2^{k}}) + kcn \\\qquad \ = nT(1) + kcn\\\qquad \ = an + cn\log n \quad (\because n = 2^k \iff k = \log n)\\\qquad \ = \Theta(n\log n)\)

※ 위 증명은 \(T(n)\)은 단조 증가 함수라는 가정하에 진행했다.
- \(T(n)\)이 단조 증가 함수라는 말의 의미는 데이터의 개수가 증가할 수록 처리 시간이 조금이라도 늘어난다는 것을 의미한다.

 

* 시간 복잡도 분석과정에서 \(n = 2^k\)와 같은 가정이 합당함을 보이는 증명은 아래 포스트를 참조하자.
 

- Asymptotic Analysis Method (점근적 분석법 - 반복대치) (URL)

[Discrete Mathematics] Asymptotic Analysis Method | 점근적 분석법 - 반복대치

 

---

Reference: 쉽게 배우는 알고리즘 (문병로 저, 한빛아카데미, 2018)