병합 정렬( Merge sort ) 알고리즘

병합 정렬 알고리즘?

안정 정렬 이자 분할 정복 알고리즘이다.

작은 단위로 리스트를 나누어 이를 정렬 및 병합하여 결국 정렬된 결과를 가지게 된다.

 

정렬 절차

• 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
• 정복(Conquer) : 부분 배열을 정렬한다.
                            부분 배열의 크기가 충분히 작지 않으면 재귀를 이용하여 다시 분할 정복 방법을 적용한다.
• 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.

추가적인 리스트가 필요하다.
각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계이다.

특징

장점

• 안정적인 정렬 방법
  데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다.
• 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
  제자리 정렬(in-place sorting)로 구현할 수 있다.
• 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 정렬 방법보다 효율적이다.

단점

• 만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.
  제자리 정렬(in-place sorting)이 아니다.
• 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.
  
  

 

구현

public static void mergeSort( int[] target ) {
    int [] sorted = new int[ array.length ];

    mergeSort( target, sorted, 0, target.length -1 );
}

public static void mergeSort( int[] target, int[] sorted, int left, int right ) {

    if( left >= right ){
        return;
    }

    // 1. 일정 크기로 쪼개기
    int mid = ( left + right ) / 2;
    mergeSort( target, sorted, left, mid );             // 왼쪽 재귀
    mergeSort( target, sorted, mid + 1, right );    // 오른쪽 재귀

    // 2. 쪼개기 다 끝나면 제일 조그만한거 부터 정렬 및 병합
    merge( target, sorted, left, mid, right );
}

public static void merge( int[] target, int[] sorted, int left, int mid, int right ){

    int leftStartIndex = left;
    int rightStartIndex = mid+1;
    int sortedIndex = left;

    // 해당 반복문은 쪼개진 두개의 리스트 중 하나의 값이 다 sorted 에 들어가면 끝난다.
    while( leftStartIndex <= mid && rightStartIndex <= right ){
        // 쪼개진 두개의 리스트의 값을 비교 해서 작은거 부터 sorted 에 넣는다.
        if( target[leftStartIndex] <= target[rightStartIndex] ){
            sorted[sortedIndex++] = target[leftStartIndex++];
        } else {
            sorted[sortedIndex++] = target[rightStartIndex++];
        }
    }

    // 두 리스트중 하나의 데이터가 남아있다! 그걸 sorted 에 넣어주자.
    if( leftStartIndex > mid ){
        for( int i = rightStartIndex; i <= right; i++ ){
            sorted[sortedIndex++] = target[i];
        }
        for( int i = leftStartIndex; i <= mid; i++ ){
            sorted[sortedIndex++] = target[i];
        }
    }

    // 정렬된 sorted 를 target에 그때그때 셋팅해준다.
    for( int i = left; i <= right; i++ ){
        target[i] = sorted[i];
    }
}

 

시간 복잡도

최악, 평균, 최상 모두 : nlogn

 

---

참조

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog