chap3-1 Merge Sort

Merge Sort

merge sort 과정

Divide - merge sort에서 배열을 divide하는데 필요한 시간은 O(1)이다. (이미 배열의 index를 알고 있기 때문에)

Conquer - 각각의 subarray를 recursive하게 sorting한다. T(n) = 2T(n/2)+cn

Combine - 각각의 subarray를 merge하면서 sorted array로 바꿔준다. O(n)

void merge_sort(int *n, int left, int right){
    int middle;

    if(left<right){
        middle=(left+right)/2;
        //conquer T(n/2)
        merge_sort(n,left,middle);
        //comquer T(n/2)
        merge_sort(n,middle+1,right);

        //combine cn
        merge(n,left,middle,right);
  
    }
}

void merge(int *n, int left, int middle,int right){
    int i,i_left,i_right;

    //right,left 둘 다 포함하므로 +1을 해준다.
    memcpy(buffer+left,n+left,sizeof(int)*(right-left+1));
    i_left=left;
    i_right=middle+1;
    i=left;
    
    while((i_left<=middle)&&(i_right<=right)){
        if(buffer[i_left]<buffer[i_right]) n[i++]=buffer[i_left++];
        else n[i++]=buffer[i_right++];
    }
    
    while(i_left<=middle) n[i++]=buffer[i_left++];
    while(i_right<=right) n[i++]=buffer[i_right++];
    
}

merge sort 결과

merge sort의 경우 최악의 경우에도 시간복잡도는 O(NlogN)이 나온다.

만약에 merge sort에서 n을 10 과 n-10으로 나누어서 계산한다면 트리의 깊이가 n/10이 되므로 시간복잡도는 O(n^2)이 될 것이다.

---

Some Derivations