[알고리즘] 분할 정복 - 합병 정렬

💡합병 정렬(Mergesort)

- n개의 정수를 가진 배열을 올림차순으로 정렬

- 배열의 원소의 개수가 1이 될때까지 반으로 분할하여 분리한 배열을 각각 따로 정렬한 후 취합

void mergesort(int n, int s[]){ // 배열을 쪼개는 함수
	const int h = n/2, m = n-h;
    int U[1...h], V[1...m]     // 배열의 인덱스를 표현(원소의 개수) 
    
    if(n>1){
    	// U배열에 S배열의 1~h번째 원소를 복사
        // V배열에 S배열의 h+1~n번째 원소를 복사
        
        mergesort(h,U);
        mergesort(m,V);
        
        merge(h,m,U,V,S);
     }
 }
 
 void merge(int h, int m, const int U[], const int V[], const int S[]) {
 	int i, j, k;
    i = 1; j = 1; k =1;
    while(i<=h && j<=m){
    	if(U[i]<V[j]) {
        	S[k] = U[i];
            i++
        } else {
        	S[k] = V[j];
            j++;
        }
        k++;
    }
    if(i>h) { 
    	// U에 있는 원소는 다 S에 들어가서 끝났기 때문에 V에 있는 원소도 마저 넣어줌(j~m까지)
    }
    else {
    	// V에 있는 원소는 다 S에 들어가서 끝났기 때문에 U에 있는 원소도 마저 넣어줌(i~k까지)
    }
  }

 

✔️ 최악의 시간 복잡도

     -  배열이 h, m개의 원소로 나눠져 있을 때, 이 두 배열을 합병하는데 걸리는 최악의 시간 복잡도는 

        분할한 배열의 원소들의 보내 배열과 역순으로 되어 있어 다 정렬해야 하는 경우이다.

        이때 정렬의 최악의 복잡도는 W(h,m) = h+m-1  

     - 전체 최악의 시간복잡도는 짜개는 시간 + 정렬하는데 걸리는 시간으로 

       W(h+m) = W(h) + W(m) + h + m -1

     -  W(n) = nlogn

 

✔️ 공간 복잡도 분석

    -  위의 알고리즘은 mergesort를 호출할 때마다 분할한 배열을 저장할 장소가 추가적으로 필요(U, V)

        2n ∈ n

    -  따라서 매번 배열을 새로 만드는 것이 아니라 배열이 low...high 인덱스만 넘겨 진행