C/C++ 병합 정렬(Merge Sort)로 배열의 인버전(Inversion) 개수 구하기

배열의 인버전(Inversion)이란?

배열의 인버전(inversion, 역전)이란 해당 배열을 정렬된 상태로 만들기 위해 필요한 교환 횟수를 의미합니다. 이미 정렬된 배열의 인버전 개수는 0이며, 반대로 역순으로 정렬된 배열에서는 인버전 개수가 최대가 됩니다.

이 문제는 두 개의 반복문을 중첩해 모든 쌍을 비교하는 단순한 방식(O(n²))보다 병합 정렬(Merge Sort)을 활용하면 O(n log n)의 시간 복잡도로 해결할 수 있습니다. 이는 대표적인 분할 정복(Divide and Conquer) 알고리즘 방식입니다.

입력 및 출력 예시

입력

숫자 시퀀스: (1, 5, 6, 4, 20)

출력

주어진 숫자들을 오름차순으로 정렬하는 데 필요한 인버전의 개수를 출력합니다.

인버전의 개수: 2
첫 번째 교환 후: (1, 5, 4, 6, 20)
두 번째 교환 후: (1, 4, 5, 6, 20)

알고리즘

merge(array, tempArray, left, mid, right)

입력 - 병합할 배열과 왼쪽(left), 중간(mid), 오른쪽(right) 인덱스
출력 - 정렬된 순서로 병합된 배열과 이 과정에서 발생한 인버전 개수

시작
   i := left, j := mid, k := left
   count := 0
   i <= mid - 1 이고 j <= right 인 동안 반복
      만약 array[i] <= array[j] 라면
         tempArray[k] := array[i]
         i와 k를 1씩 증가
      아니면
         tempArray[k] := array[j]
         j와 k를 1씩 증가
         count := count + (mid - i)
   반복 종료
   왼쪽 부분에 남은 요소가 있는 동안
      tempArray[k] := array[i]
      i와 k를 1씩 증가
   반복 종료
   오른쪽 부분에 남은 요소가 있는 동안
      tempArray[k] := array[j]
      j와 k를 1씩 증가
   반복 종료
   count 반환
끝

mergeSort(array, tempArray, left, right)

입력 - 주어진 배열과 임시 배열, 배열의 왼쪽·오른쪽 인덱스
출력 - 정렬 과정에서 발생한 총 인버전 개수

시작
   count := 0
   만약 right > left 라면
      mid := (right + left) / 2
      count := mergeSort(array, tempArray, left, mid)
      count := count + mergeSort(array, tempArray, mid+1, right)
      count := count + merge(array, tempArray, left, mid+1, right)
   count 반환
끝

C/C++ 예제 코드

#include <iostream>
using namespace std;

int merge(int arr[], int temp[], int left, int mid, int right) {
    int i, j, k;
    int count = 0;
    i = left;   // 첫 번째(왼쪽) 배열의 위치를 가리키는 인덱스
    j = mid;    // 두 번째(오른쪽) 배열의 위치를 가리키는 인덱스
    k = left;   // 병합된 배열의 위치를 가리키는 인덱스
    while ((i <= mid - 1) && (j <= right)) {
        if (arr[i] <= arr[j]) { // 왼쪽 요소가 더 작거나 같으면 그대로 복사
            temp[k++] = arr[i++];
        } else { // 오른쪽 요소가 먼저 배치되므로 역전 발생
            temp[k++] = arr[j++];
            count += (mid - i); // 왼쪽에 남은 모든 요소와 역전 관계 성립
        }
    }
    while (i <= mid - 1)  // 왼쪽 리스트에 남은 요소 처리
        temp[k++] = arr[i++];
    while (j <= right)    // 오른쪽 리스트에 남은 요소 처리
        temp[k++] = arr[j++];
    for (i = left; i <= right; i++)
        arr[i] = temp[i]; // 임시 배열의 내용을 원본 배열로 복사
    return count;
}

int mergeSort(int arr[], int temp[], int left, int right) {
    int mid, count = 0;
    if (right > left) {
        mid = (right + left) / 2;   // 배열의 중간 인덱스 계산
        count = mergeSort(arr, temp, left, mid);   // 왼쪽 하위 배열 정렬
        count += mergeSort(arr, temp, mid + 1, right);   // 오른쪽 하위 배열 정렬
        count += merge(arr, temp, left, mid + 1, right);   // 두 하위 배열 병합
    }
    return count;
}

int arrInversion(int arr[], int n) {
    int temp[n];
    return mergeSort(arr, temp, 0, n - 1);
}

int main() {
    int arr[] = {1, 5, 6, 4, 20};
    int n = 5;
    cout << "Number of inversions are " << arrInversion(arr, n);
}

실행 결과

Number of inversions are 2

동작 원리 정리

핵심은 병합(merge) 단계에 있습니다. 왼쪽 부분 배열의 요소 arr[i]가 오른쪽 부분 배열의 요소 arr[j]보다 크다면, 왼쪽 부분 배열에서 i부터 mid - 1까지의 모든 요소가 arr[j]와 역전 관계에 있습니다. 따라서 한 번의 비교만으로 여러 개의 인버전을 동시에 셀 수 있으며, 덕분에 전체 시간 복잡도가 O(n log n)으로 줄어듭니다.