Merge Sort (recursive)

1. Problem

- n개의 key를 오름차순으로 정렬하자

 

2. Input

1) 양수 n

2) 배열 S indexed from 1 to n

 

3. Output

1) 오름차순으로 정렬된 배열 S

 

4. PseudoCode

void mergesort(int n, keytype[] S){
    if(n>1){
        const int h = n/2, m = n-h;
        keytype U[1..h], V[1..m];
        copy S[1]~S[h] to U[1]~U[h];
        copy S[h+1]~S[n] to V[1]~V[m];
        mergesort(h,U);
        mergesort(m,V);
        merge(h,m,U,V,S);
    }
}
 
// 정렬된 배열 U와 V의 요소를 합해서 정렬된 S를 만든다.
void merge(int h, int m, const keytype[] U, const keytype[] V, keytype[] S){
    index 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) // V의 남은 요소를 S의 뒤쪽에 배치
        copy V[j]~V[m] to S[k]~S[h+m];
    else // U의 남은 요소를 S의 뒤쪽에 배치
        copy U[i]~U[h] to S[k]~S[h+m];
}

 

5. Example

class Test {
    public static void main(String[] args){
    	int[] arr = {27,10,12,20,25,13,15,22};
    	mergesort(arr.length, arr);
    	for(int i : arr)
    		System.out.print(i + " "); // 10 12 13 15 20 22 25 27 
    }
    
    static void mergesort(int n, int[] S) {
    	if(n>1) {
        	int h = n/2, m = n-h;
        	int[] U = new int[h], V = new int[m];
        	System.arraycopy(S, 0, U, 0, h);
        	System.arraycopy(S, h, V, 0, m);
        	mergesort(h, U);
        	mergesort(m, V);
        	merge(h, m, U, V, S);    		
    	}
    }
    
    static void merge(int h, int m, int[] U, int[] V, int[] S) {
    	int i=0, j=0, k=0;
    	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)
    		System.arraycopy(V, j, S, k, h+m-k);
    	else
    		System.arraycopy(U, i, S, k, h+m-k);
    }
}