Merge Sort

Pseudocode

mergeSort

public static void mergeSort(int n, keytype[] s)
    {
        if(n>1){ //종료 조건 : 나눌 수 없을 때 까지 나눔
            const int h=floor(n/2), m=n-h; //반으로 자름
            keytype[] U=new keytype[0..h-1]; //크기 h
            keytype[] V=new keytype[0..m-1]; //크기 m

            //Divide
            copy S[0:h-1] to U[0:h-1];
            copy S[h:n-1] to V[0:m-1];
            //Conquer
            mergeSort(h,U);
            mergeSort(m,V);
            //Combine
            merge(h,m,U,V,S);
        }
    }

merge

 public static void merge(int h, int m, keytype[] U, keytype[] V, keytype S)
    {
        index i=0, j=0, k=0;
        while(i<h && j<m){
            if(U[i]<V[j]){ //U배열의 값이 더 작으면 그 값을 S배열에 넣고 i+1인덱스로 
                S[k]=U[i];
                i++;
            }else{
                S[k]=V[j];
                j++;
            }
            k++;
        }
        if(i>=h) //U배열의 값이 다 S로 옮겨졌으면 V배열의 남은 부분을 S뒤에 붙인다.
            copy V[j:m-1] to S[k:h+m-1];
        else
            copy U[i:h-1] to S[k:h+m]-1;
    }

시간 복잡도와 공간 복잡도

• Best, Average, Worst case 시간 복잡도 : O(nlogn)

• 공간 복잡도 : O(n)

• Best case Time Complexity of Merge
  : 왼쪽 배열(U)의 모든 원소가 오른쪽 배열(V)의 첫번째 원소보다 작을 때
  -> 왼쪽 배열(U)의 크기(h) 만큼 비교가 일어난다.
  => 시간 복잡도 : h

• Worst case Time Complexity of Merge
  : 왼쪽 배열(U)의 마지막 원소를 제외한 원소들이 오른쪽 배열(V)의 첫번째 원소보다 작고, 왼쪽 배열(U)의 마지막 원소가 오른쪽 배열(V)의 나머지 원소보다 클 때
  -> 왼쪽 배열의 원소들을 다 비교(h)하고 오른쪽 배열의 첫원소 빼고 다 비교(m-1)하게된다.
  => 시간 복잡도 : h+m-1

• WortCase Time Complexity of MergeSort