Merge Sort (recursive, less memory, in-place)

1. Problem

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

 

2. Input

1) 양수 low

2) 양수 high

3) 배열 S indexed from 1 to n

 

3. Output

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

 

4. PseudoCode

void mergesort2(index low, index high, keyptype[] S){
    index mid;
    if(low<high){
        mid = floor((low+high)/2);
        mergesort2(low, mid);
        mergesort2(mid+1,high);
        merge2(low, mid, high, S);
    }
}

void merge2(index low, index mid, index high, keytype[] S){
    index i=low, j=mid+1, k=low;
    keytype U[low..high];
    while(i<=mid && j<=high){
        if(S[i]<S[j]){
            U[k] = S[i]; i++;
        } else{
            U[k] = S[j]; j++;
        }
        k++;
    }
    if(i>mid)
        move S[j]~S[high] to U[k]~U[high];
    else
        move S[i]~S[mid] to U[k]~U[high];
    move U[low]~U[high] to S[low]~S[high];
}

 

5. Example

class Test {
    public static void main(String[] args){
    	int[] arr = {27,10,12,20,25,13,15,22};
    	mergesort2(0, arr.length-1, arr);
    	for(int i : arr)
    		System.out.print(i + " "); // 10 12 13 15 20 22 25 27 
    }
    
    static void mergesort2(int low, int high, int[] S) {
    	if(low<high) {
        	int mid = (low+high)/2;
        	mergesort2(low, mid, S);
        	mergesort2(mid+1, high, S);
        	merge2(low, mid, high, S);
    	}
    }
    
    static void merge2(int low, int mid, int high, int[] S) {
    	int i=low, j=mid+1, k=low;
    	int[] U = new int[S.length];
    	while(i<=mid && j<=high) {
    		if(S[i]<S[j]) {
    			U[k] = S[i]; i++;
    		} else {
    			U[k] = S[j]; j++;
    		}
    		k++;
    	}    		
    	if(i>mid)
    		System.arraycopy(S, j, U, k, high-k+1);
    	else
    		System.arraycopy(S, i, U, k, high-k+1);
    	System.arraycopy(U, low, S, low, high-low+1);
    }
}

---

[추가 정리]

1. Example

// 예시: 2 3 7 6 1 8 5 4
// (2) (3) (7) (6) (1) (8) (5) (4)
//  (2 3)   (6 7)   (1 8)   (4 5)
//   (2 3 6 7)        (1 4 5 8)
//       1 2 3 4 5 6 7 8

 

2. Code

// main()
int[] arr = {6, 3, 5, 9, 1, 10, 7, 2, 4, 8}; // 10개의 요소
mergesort(arr, 0, arr.length-1);

static void mergesort(int[] arr, int start, int end) {
    // 원소의 개수가 2개 이상일 때만 반으로 나눈다.
    if(start<end) {
        int mid = (start+end)/2;
        mergesort(arr, start, mid);  // arr를 반으로 나눈 다음
        mergesort(arr, mid+1, end);
        merge(arr, start, mid, end); // 합친다.
    }
}
    
static void merge(int[] arr, int start, int mid, int end) {
    int[] sorted = new int[end-start+1];
    int i = start, j = mid+1, k = i; // 반으로 나눈 값들을 비교하면서
    while(i<=mid && j<=end) {        // 임시 배열에 차례대로 저장한다.
        if(arr[i]<=arr[j])           // 앞쪽 요소가 작다면
            sorted[k] = arr[i++];    // 앞쪽 요소를 임시 배열에 저장하고
        else                         // 뒷쪽 요소가 작다면
            sorted[k] = arr[j++];    // 뒷쪽 요소를 임시 배열에 저장한다.
        k++;
    }
    if(i>mid)                        // 앞쪽 요소를 다 저장했다면
        for(int l=j ; l<=end ; l++)  // 뒷쪽에 남은 요소를 임시 배열에 저장한다.
            sorted[k++] = arr[l];
    else                             // 뒷쪽 요소를 다 저장했다면
        for(int l=i ; l<=mid ; l++)  // 앞쪽에 남은 요소를 임시 배열에 저장한다.
            sorted[k++] = arr[l];
    for(i=start, j=0; i<=end ; i++, j++) // 임시 저장된 배열의 값을
        arr[i] = sorted[j];              // 원 배열에 저장한다.    
}
    
// 다시 main()
// 정렬 확인
for(int i : arr)
    System.out.print(i+","); // 1,2,3,4,5,6,7,8,9,10,

- 10개의 요소를 정렬할 때 살펴봐야 하는 총 횟수는 10 * 2번의 비교 연산을 해야 한다.
- n개의 요소라면 비교 연산의 총 횟수는 n*lgn번이다.
- 그러므로 시간 복잡도는 O(n*lgn)를 따른다.
- 대부분의 상황에서는 퀵 정렬이 빠른 편이지만, 어떤 n이어도 n*lgn을 보장한다는 점에서 효율적이라고 평가받는다.