[알고리즘] 합병 정렬, Merge Sort | 설계 및 분석

합병 정렬 알고리즘이란? 

  크기가 n인 배열을 원소가 하나 밖에 남지 않을 때까지 계속 반으로 쪼갠 후 다시 크기 순으로 정렬 하면서 원래 크기의 배열로 합치는 정렬 알고리즘

 

알고리즘 설계 전략

  배열 원소가 하나 남을 때 까지 배열을 재귀적으로 쪼갠다. (Divide)

  쪼개진 배열들을 정렬하면서 다시 합친다. (Conquer)

 

 

출처 : foundations of algorithms, 도경구역

 

알고리즘 수도코드

void mergesort(int n, keytype S[]) {
  if (n > 1) {
    const int h = ⌊n/2⌋, m= n - h;
    keytype U[1..h], v[1..m];
    
    //S를 반으로 쪼개 왼쪽은 U에 오른쪽은 V에 저장
    copy S[1] through S[h] to U[1] through U[h];
    copy S[h+1] through S[n] to V[1] through V[m];
    
    mergesort(h,U); //재귀(왼쪽)
    mergesort(m,V); //재귀(오른쪽)
    merge(h,m,U,V,S); //정렬돼서 돌아온 두 배열을 합침
  }
}

void merge(int h, int m, const keytype u[], const keytype v[], keytype S[])
{
  index i, j, k;
  i=1, j=1, k=1;
  
  while(i <= h && j <= m) { //정렬하면서 두 배열 u,v를 합쳐 S에 담는다.
    if(u[i] < v[j]) { // ①
      S[k] = u[i];
      i++;
    }
    else { // ②
      S[k] = v[i];
      j++;
    }
    k++;
  }
  if(i > h)
    copy v[j] through v[m] to S[k] through S[h + m];
  else
    copy u[i] through u[h] to S[k] through S[h + m];
}

 

알고리즘 성능 분석

basic operation: 두 배열 u와  v를 합칠 때 수행되는 비교 연산(위 코드 ①, ② 부분)

 

merge 함수와 merge sort 함수 중 우선 merge 알고리즘의 성능부터 분석해보자.

 

  merge 함수 성능

1) merge 함수 최선의 경우

  당연하게도, 아래와 같이 배열 u와 v가 이미 정렬이 되어있는 경우가 최선이다. 

최선의 경우인 배열의 예

 

위 배열의 비교 횟수

 

∴ B(h+m) =  ⌊(h+m)/2⌋ (h는 u의 길이, m은 v의 길이)

 

2) merge 함수 최악의 경우

  최악의 경우는 아래와 같다. 

최악의 경우인 배열의 예

 

위 배열의 비교 횟수

 

(마지막남은 8은 비교하지 않고 그대로 옮겨진다.)

 ∴ w(h + m) = h + m - 1

     n = h + m일 때, w(n) = n - 1

 

  merge sort 함수 성능

  위에서 merge 함수의 최악의 경우를 구한 값을 바탕으로 merge sort 함수의 최악의 경우 성능을 구해보자.

 

<재귀 호출이 있는 알고리즘의 성능 분석 방법>
① 복잡도 함수의 점화식 수립한다.
② 수립한 점화식을 일반화한다.

 

① 복잡도 함수의 점화식 수립

  결론부터 얘기하면, w(h+m) = w(h) + w(m) + h+m-1 이다.

  merge sort 함수를 보면 마지막 부분에 아래와 같이 mergesort(h,U)로 왼쪽 배열을 정렬하고, mergesort(m,V)로 오른쪽 배열을 정렬한 후, 이 두 배열을 최종적으로 merge()에서 합치면서 재정렬한다.

 

mergesort(h,U); //w(h)
mergesort(m,V); //w(m)
merge(h,m,U,V,S); //h+m-1

 

따라서 왼쪽 배열에서 w(h), 오른쪽 배열에서 w(m), merge()함수에서 방금 알아보었던 최악의 경우 (h+m-1)의 합이 된다.

 

n  =h+m이라고 가정하면,

w(n)=w( ⌊n/2⌋ ) + w( ⌈n/2⌉ ) + (n - 1) , (n=2^k, k≥0) 이다.

 

∴ w(n) = w(n/2) + w(n/2) + n - 1 

          =  2 x w(n/2) + n - 1

 

이제 이 점화식을 일반화해보자.

 

② 점화식 일반화

위에서 도출해낸 w(n)=2 x w(n/2) + n - 1 에서, n=2^k라고 가정했으므로 n 대신 2^k를 넣으면

w(2^k) = 2 x w(2^k-1) + 2^k - 1

w(2^k)를 t_k로 치환하여 식을 일반화할 수 있다. 과정은 다음과 같다.

 

출처 : foundations of algorithms, 도경구역

w(n) = n x w(1) + n lg n - (n - 1)

∴ w(n) ∈ Θ(n lg n)