[Sort]Merge Sort(합병 정렬)

설명

• 두개의 정렬된 리스트가 주어졌을 때 두 개의 리스트를 합치면서 정렬하는 방법
• Divide and Conquer (분할정복) 알고리즘의 방법이다.

예제

Psuedo Code

MERGE_SORT(A, p, r) // A는 정렬할 List p,r은 처음과 끝 index
    if p < r 
        q = [(p + r) / 2] // 중간값을 찾아 divide and conquer
        MERGE_SORT(A, p, q) // List의 왼쪽 부분을 정렬
        MERGE_SORT(A, q+1, r) // List의 오른쪽 부분을 정렬
        MERGE(A, p, q, r) // 왼쪽과 오른쪽을 합치면서 정렬


MERGE(A, p, q, r)  //A는 정렬할 List p는 처음 index, r은 마지막 index, q는 중간 index
    n1 = q - p + 1 // p 부터 q 까지의 크기
    n2 = r - q // q + 1 부터 r까지의 크기
    let L[1 ... n1 + 1] and R[1 ... n2 + 1] be new arrays
    for i = 1 to n1
        L[i] = A[p + i - 1] // L 리스트를 A의 index p 부터 q 로 초기화
    for j = 1 to n2
        L[j] = A[q + j] // R 리스트를 A의 index q + 1 부터 r 까지로 초기화

       //한쪽리스트가 먼저 다 Merge 될 경우 나머지 List의 값들을 inf와 비교해 Merge하기 위함 
    L[n1 + 1] = inf
    R[n2 + 1] = inf


    i = 1
    j = 1
    // 왼쪽 리스트의 값과 오른쪽 리스트의 값을 비교해가며 정렬
    for k = p to r
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
          else
            A[k] = R[j]
            j = j + 1

시간 복잡도

• 분할 단계
  연산 수행 X
• 비교 단계
  Divide의 깊이 (Recursion 호출 횟수)  → \(log_2N\)
  각각의 깊이에서의 비교 횟수 → \(N\)
  즉, 환 호출의 깊이 만큼의 합병 단계 * 각 합병 단계의 비교 연산 = \(Nlog_2N\)
• 이동 단계
  깊이 (Recursion 호출 횟수)  → \(O(log_2N)\)
  각각의 깊이에서 이동 횟수 →  \(2N\) 번
  즉, 순환 호출의 깊이 만큼의 합병 단계 * 각 합병 단계의 이동 연산 = \(2Nlog_2N\)
• 종합
  \(Nlog_2N + 2Nlog_2N = O(Nlog_2N)\)

Best Case & Worst Case 모두 \(O(Nlog_2N)\) 의 시간 복잡도를 가진다.

 

장점 

• 데이터의 민감하지 않다.
  → Best & Worst 의 시간 복잡도가 똑같다.

단점

• 배열을 복사해 사용해야 한다
  → 메모리의 낭비가 있다.

참고 자료

• Introduction to Algorithms, 3rd Ed
• Heee's Development Blog