병합 정렬(Merge Sort)

  합병정렬이라고도 불리는 병합정렬에 대해서 알아보자.

1. 정의 🎃

병합 정렬

  병합정렬이란 정렬해야 하는 배열을 가장 작을 때까지 나누고, 그 시점부터 인접한 부분배열끼리 비교하며 정렬하는 알고리즘이다.
  해당 알고리즘은 분할 정복(Divide and Conquer) 알고리즘을 기반으로 한다. (분할 정복(Divide and Conquer)이란 문제를 분할하고, 분할한 문제를 정복하여 합치는 것이다.)

 

2. 동작 방식 🎪

1. 주어진 배열을 절반으로 분할하여 부분배열로 나눈다. - 분할(Divide)
2. 해당 부분배열의 길이가 1이 될 때까지 계속해서 1번 과정을 반복한다.
3. 인접한 부분 배열끼리 합친다. - 정복(Conquer)

 

  위의 그림을 통해 알 수 있듯이 크기가 1이 될 때까지 분할이 진행된다. 그리고 인접한 배열끼리 합치면서 계속해서 정렬이 이루어진다. 그러면 최종적으로 정렬된 배열을 얻을 수 있다. 병합할 때 어떻게 정렬이 되는지 "마지막 conquer 과정인 '2 4 6 8'과 '3 5 7 9'를 병합하는 과정"을 통해 조금 더 자세히 알아보자.

  합병을 시킬 두 개의 배열은 이미 정렬이 되어 있는 상태이다. 그러므로 병합을 하는 과정에서는 자신이 속한 배열의 원소들과 비교를 할 필요 없이 인접한 부분 배열의 원소들만 비교를 해주면 된다. 원소끼리 비교를 해나가면서 작은 것이 먼저 배치된다고 생각하면 된다.

  예시에서는 왼쪽과 오른쪽이 순서대로 한 개씩 선택이 되고 있는데, 꼭 그런 것만은 아니다. 비교를 통해 작은 거를 선택하는 것이다. '2 8'과 '4 6'이 병합되는 것을 보면 쉽게 알 수 있다.

 

3. 구현(JAVA) 🎭

public void main(String[] args) {
    int[] array = {8, 2, 6, 4, 7, 3, 9, 5};

    mergeSort(array, 0, array.length - 1);
}

void mergeSort(int[] array, int left, int right) {
    // 더 이상 분할 할 수 없는 경우 
    // (크기가 1인 경우) 
    if(left == right) {
        return;
    }

    int mid = (left + right) / 2;

    // 분할 (Divide)
    mergeSort(array, left, mid);
    mergeSort(array, mid + 1, right);

    // 분할된 배열을 병합하기 - 정복(Conquer)
    merge(array, left, mid, right);
}

// 분할된 배열을 병합해주는 과정에서
// 정렬이 이루어진다.
void merge(int[] array, int left, int mid, int right) {
    // 왼쪽 부분배열
    int[] L = Arrays.copyOfRange(array, left, mid + 1);
    // 오른쪽 부분배열
    int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);

    // 왼쪽 부분배열의 인덱스 번호
    int l = 0;
    // 오른쪽 부분배열의 인덱스 번호
    int r = 0;
    // 병합되어진 배열의 인덱스 번호
    int idx = left;

    int leftLength = L.length;
    int rightLength = R.length;

    // 두 개의 배열에서 원소를 비교해야 하는 경우
    // 각각의 배열은 정렬되어진 상태이므로, 두 개의 배열의 원소만 비교하면 됨 
    while(l < leftLength && r < rightLength) {
        if(L[l] <= R[r]) {
            array[idx] = L[l++];
        }
        else {
            array[idx] = R[r++];
        }
        idx++;
    }

    // 왼쪽 부분배열이 남아 있는 경우 
    // 병합하여 만들어질 배열에 넣기
    while(l < leftLength) {
        array[idx++] = L[l++];
    }

    // 오른쪽 부분배열이 남아 있는 경우
    // 병합하여 만들어질 배열에 넣기
    while(r < rightLength) {
        array[idx++] = R[r++];
    }
}

 

4. 시간복잡도 & 공간복잡도 🎠

1. 시간복잡도

  '분할'할 때와 '병합(정복)'할 때를 나누어서 생각해 보자.

[분할]

  크기가 1인 배열까지 분할을 해야 하므로 힙정렬에 의해서 O(logN)의 시간이 걸린다.

[병합(정복)]

  i번째 레벨에는 2^i개의 부분배열이 있다. 그리고 각 부분배열에는 N / 2^i 개의 원소가 있다. 하나의 병합된 배열을 만들기 위해서는 두 개의 부분 배열의 원소 개수만큼 비교하여 만들 수 있다.
  그러면 i번째 레벨에서 하나의 병합된 배열을 만들기 위해서는 N / 2^i * 2의 비교가 일어나고, 총 2^i / 2번 해줘야 한다.

(N / 2^i * 2) * ( 2^i / 2) = N

  그리고 이것을 트리의 높이인 logN번 수행해야 하므로 최종적으로 O(N logN)의 시간이 걸린다.

  그러므로 시간복잡도는 O(N logN)이다.

	최선(BEST)	평균(AVERAGE)	최악(WORST)
시간복잡도	O(N logN)	O(N logN)	O(N logN)

2. 공간복잡도

  정렬할 배열과 같은 크기의 N의 새로운 배열이 필요하므로 공간복잡도는 O(2N)이다.

 

5. 장점 & 단점 🥁

1. 장점

• 최악의 경우에도 시간복잡도가 O(N log N)이다
• 안정정렬이다.

2. 단점

• 추가적인 메모리 공간이 필요하다.
• 보조 배열에서 원본배열로 복사하는 과정은 매우 많은 시간을 소비하기 때문에 데이터가 많을 경우 상대적으로 시간이 많이 소요된다.

 

해당 글은 Stranger님의 합병정렬/병합정렬(Merge Sort)을 참고하였습니다.