Merge Sort

* 배열의 인덱스가 1부터 시작한다고 가정합니다.

([1] = 1번째 와 같이 이해하기 쉽도록)

 

- 알고리즘 정의

주어진 배열을 정렬하는 알고리즘.

단, 정렬하는 방법이 Divide and Conqure 방식이다.

배열을 최대한 작게 쪼개고, 병합하는 과정에서 정렬하여 병합하는 방식이다.

 

- Pseudocode

public static void mergeSort (int n, keyType[] S) {
   if (n <= 1) return;
   
   const int h = floor(n/2);  // 거의 반으로 쪼개기
   const int m = n - h;       // 나머지 반
   keyType[] U = new keyType[1..h];
   keyType[] V = new keyType[1..m];
   
   // Divide
   copy S[1:h] to U[1:h];
   copy S[h+1, n] to V[1:m];
   // Conquer
   mergeSort(h, U);
   mergeSort(m, V);
   // Combine
   merge(h, m, U, V, S);
}

public static void merge (int h, int m,
                          keyType[] U, keyType[] V, keyType[] S) {
    index i = 1;
    index j = 1;
    index k = 1;
    
    // 작은 순서대로 S(Sorted)배열에 추가
    while (i <= h && j <= m) {
        if (U[i] < V[j]) S[k] = U[i++];
        else S[k] = V[j++];
        k++;
    }
    
    // 최적화
    if (i > h) {
        // U 배열이 먼저 끝까지 탐색된 경우
        copy V[j:m] to S[k:h+m];
    } else {
        // V 배열이 먼저 끝까지 탐색된 경우
        copy U[i:h] to S[k:h+m];
    }
}

mergeSort 파트에서 정렬되지 않은 배열 S를 반으로 쪼개어 U, V 배열에 저장한다.

각 배열의 크기는 h, m이 된다.

쪼개는 과정을 배열의 크기가 1이 될 때 까지 반복하여 쪼갠다.

이후 merge  파트에서 배열을 정렬하며 합치게 된다.

U[i], V[j]를 비교해가며 작은 값부터 S[k]에 채워나간다.

이후 U, V 배열 중 하나가 탐색이 완료되면, 다른 배열 중 탐색되지 않는 원소를 S배열에 바로 채워 넣는다.

 

- Time complexity (merge part)

Basic Operation: U[i] < V[j]

Input Size: h, m, sizeof U, V

 

* Best case: B(h, m) = min(h, m)

이미 정렬된 경우, U 또는 V 배열의 크기만큼만 비교하면 끝난다.

 

* Worst case: W(h, m) = h + m - 1

S에 할당하는 과정에서 모두 비교가 일어날 경우.

즉, 정렬된 상태에서 1 또는 2번째로 큰 값만 다른 배열로 들어간 경우.

 

- Time complexity (mergeSort part)

Basic Operation: call merge

Input Size: n (n = 2^k라 가정)

 

* Worst case: 

(Best case도 비슷한 방식으로 진행)

[Θ(n lg n)]