[정렬 #2] 합병 정렬(Merge Sort) w.Java

합병정렬(또는 병합정렬)은 비교기반 정렬 알고리즘이다.

분할(Divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

정복(Conquer): 각 부분 리스트를 재귀적으로 합병 절렬을 이용하여 정렬한다.

결함(Combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한디ㅏ. 이때 정렬 결과가 임시배열에 저장된다.

복사(Copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다. 

 

특징 및 장점

일반적인 방법으로 구현했을 때, 안정정렬이다.

Linked list를 정렬할 때 사용하면 효율적이다. 

분할 정복 알고리즘(그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법, 보통 재귀함수를 통해 구현)이다.

배열일 경우 Θ(n)의 추가 공간이 필요하고, linked list의 경우 Θ(lg(n))의 추가 공간이 필요하다. 

단점

in-place 정렬이 아니다.

레코드가 많을 경우 이동 횟수가 많으므로 비효율적이다.

 

Java 로 구현

// merge sort range : [low ~ high]
// array A[] has the items to sort; array B[] is a work array

void mergeSort(int A[], int low, int high, int B[]){

    // 1. base condition
    if(low >= high) return;
    
    // 2. divide
    int mid = (low + high)/2;

    // 3. conquer
    mergeSort(A, low, mid, B);
    mergeSort(A, mid+1, high, B);

    // 4. combine
    int i = low, j = mid+1, k = low;

    for(; k<= high; ++k){
        if(j > high) B[k] = A[j++];
        else if(i > mid) B[k] = A[j++];
        else if(A[i] <= A[j]) B[k] = A[i++];
        else B[k] = A[j++];
    }
    
    // 5. copy
    for(i=low; i<= high; ++i){
        A[i] = B[i];
    }
}

 

시간 복잡도

최선: nlogn

평균: nlogn

최악: nlogn

 

Reference

https://ko.wikipedia.org/wiki/합병_정렬

https://www.toptal.com/developers/sorting-algorithms/merge-sort