무게를 모르는 추가 있다면, 몇 번의 비교로 그 순서를 알아낼 수 있을까요?

추를 양쪽에 하나씩 달 수 있는 저울이 있다고 해봅시다. 그렇다면 저울을 얼마나 적게 쓸 수 있는지 알아내는 것은 중요한 문제가 됩니다. 왜냐면 비교를 통해 데이터를 소트sort하는, 비교 기반comparison-based 소팅 알고리즘이 얼마나 빠를 수 있는지와 관련이 있기 때문입니다.

추가 세 개일 때를 예를 들어본다면, 저울을 최대 세 번 써야한다는 것을 알게 됩니다.

추의 무게가 각각 $w_1$, $w_2$, $w_3$이라고 하면, 저울을 사용하는 방법은 다음 두 가지 경우로 정리됩니다.

1. 운이 좋아서 두 번으로 끝난 경우: 예를 들어 $w_1 < w_2$이고, $w_2 < w_3$인 걸 알아낸 경우.

2. 그렇지 않아서 세 번이 필요한 경우: 예를 들어 $w_1 < w_2$이고, $w_2 > w_3$이어서, 나머지 $w_1$와 $w_3$의 순서를 알아내야 할 때.

그런데 이렇게 생각하는 대신 트리tree를 그려볼 수도 있습니다. 저울이 항상 두 가지 결과, 오른쪽이 내려오거나 그렇지 않은 경우를 가진다고 생각해봅시다. 그러면 저울을 쓸 때마다 두 가지의 미래가 존재합니다. 따라서 각 노드node가 두 개의 자식 노드를 갖는 바이너리 트리binary tree로 나타낼 수 있게 됩니다.

여기서 각 노드는 저울의 사용을 나타내고, 마지막에 나타나는 노드, 즉 리프 노드leaf node는 결정된 추의 순서를 나타냅니다. 이렇게 결정 과정을 나타내는 트리를 결정 트리 혹은 디시전 트리decision tree라고 부릅니다.

앞서 운이 좋아 두 번으로 끝난 경우는, 위 트리의 가장 왼쪽 리프 노드에 해당합니다. 그리고 세 번이 필요했던 경우는 왼쪽에서 두 번째와 세 번째에 해당합니다. 여기서 볼 수 있듯이, 노드의 높이가 곧 저울의 사용 횟수가 됩니다.

이렇게 추가 세 개인 경우 디시전 트리를 그리는 것은 어렵지 않지만, 네 개를 넘어가기 시작하면 점점 쉽지 않아집니다. 왜냐면 $n$ 개의 추가 가질 수 있는 순서는 팩토리얼factorial, 즉 $n!=n {\cdots} 3 {\cdot} 2 {\cdot} 1$ 개로 빠르게 늘어나기 때문입니다. 추가 다섯 개면 $5!=5{\cdot}4{\cdot}3{\cdot}2{\cdot}1=120$ 개나 되는 리프 노드를 그려야 합니다.

하지만 디시전 트리의 높이는 적어도 얼마인지 알아낼 수 있습니다. 그리고 그 높이가 바로 저울의 사용 횟수를 의미하기 때문에, 이로부터 저울을 적어도 몇 번 써야하는지, 나아가 비교 기반 소팅 알고리즘의 시간 복잡도가 적어도 얼마인지 알게 됩니다.

바이너리 트리의 기본적인 성질은, 리프 노드가 $n$ 개이면 높이는 $\lg n$ 이상이라는 것입니다. 높이가 $n-1$이면 리프 노드는 기껏해야 $2^{n-1}$ 개이기 때문입니다.

디시전 트리는 리프 노드가 $n!$ 개이므로 높이는 $\lg (n!)$ 이상이 됩니다. 그리고 스털링 근사Stirling’s approximation를 통해 $\lg (n!) \sim n \lg n = \Theta(n \lg n)$을 얻습니다.

물론 디시전 트리가 아니라 바이너리 트리의 특징에서 이끌어낸 결과지만, 디시전 트리도 바이너리 트리이므로 $\lg (n!)$ 이상의 높이를 가집니다. 그러므로 모든 비교 기반 소팅 알고리즘은 최악의 경우에 이 이상의 시간 복잡도, 즉 $\Omega(n \lg n)$을 갖게 됩니다. 다시 말해, $O(n)$의 시간이 걸리는 알고리즘은 이론적으로 존재할 수 없게 됩니다.

한편, 이론적으로 시간 복잡도의 한계를 구한 것과, 그런 시간 복잡도를 갖는 알고리즘을 생각해내는 것은 별개의 일이지만, 실제로 최악의 경우에 $\Theta(n \lg n)$의 시간이 드는 머지 소트merge sort가 있습니다. 이론적으로 적어도 $\Omega(n \lg n)$의 시간 복잡도를 가진다는 사실에 비추어본다면, 이 알고리즘은 최악의 경우에 최적의 시간 복잡도를 가졌다고 말할 수 있습니다.

여기서는 머지 소트를 다른 라이브러리 도움 없이 자바Java로 구현해보겠습니다. 나아가 한 가지 개선 방법으로, 이전 글에서 만들었던 인서션 소트insertion sort를 섞어보겠습니다. 또한 머지 소트를 간단히 응용해 인버전inversion을 세는 알고리즘을 만들어보겠습니다.

작은 문제로 나눠서 해결하기

머지 소트의 아이디어는, 소트된 두 카드 덱을 하나의 덱으로 소트하는 문제로 소개할 수 있습니다.

먼저, 각 덱에서는 맨 앞의 카드가 가장 낮다는 사실을 이용합니다. 그렇다면 두 덱의 맨 앞의 카드 중 더 낮은 것이 전체 중에서도 가장 낮은 것입니다. 따라서 그것을 가져와 맨 앞에 놓습니다. 그리고 이를 반복하면, 자연스럽게 하나의 덱으로 합치게 되면서 소트하게 됩니다. 이 과정을 머지merge한다고 부릅니다.

그런데 이렇게 머지 하기 전에는, 작은 크기의 덱이 미리 소트되어 있어야 하는데요. 덱에 카드가 하나밖에 없다면 이미 소트되었다고 볼 수 있습니다. 따라서 머지 소트가 해야할 일은, 먼저 모든 카드를 하나씩 덱으로 나눈 다음, 이로부터 머지하며 소트하는 것입니다.

이런 카드가 실제로는 배열로 주어진다고 한다면, 이 아이디어를 표현한 수도코드pseudocode는 이렇습니다.

이전 글에서처럼, 구간을 표현하는 두 인덱스는 반열린구간half-open interval $[\textit{begin}, \textit{end})$, 즉 구간의 시작 $\textit{begin}\,$은 포함하고 마지막 $\textit{end}\,$는 제외한 것을 나타냅니다. 또한 바닥 함수 혹은 플로어 함수floor function $\lfloor x \rfloor$는, $\lfloor 3.1 \rfloor = 3$ 처럼 소수점을 버리기 위해 쓰였습니다.

수도코드가 보여주듯이, 머지 소트는 데이터를 바로 소트하는 것이 아니라, 일단 반씩 나누어 다음 재귀에 맡깁니다. 그러다가 배열의 크기가 하나가 되어서야 본격적인 소트를 시작합니다. 그러면 머지를 통해 소트된 부분이 점점 커지면서 소트가 끝납니다.

마지막 단계에 쓰이는 머지 알고리즘은 카드 예시에서 봤던 두 덱을 합치는 과정을 수행합니다. 머지할 두 구간이 $[\textit{begin}, \textit{mid})$, $[\textit{mid}, \textit{end})$로 주어진다고 하면, 머지 알고리즘의 수도코드는 이렇습니다.

반복문에서는 매 반복마다 더 낮은 데이터를 가져옵니다. 여기서 두 데이터의 순서가 같은 경우를 잘 처리하면, 소팅 알고리즘이 기존 데이터의 상대적인 순서를 유지하도록, 즉 스테이블stable하도록 만들 수 있습니다.

여기선 머지 소트를 스테이블하게 만들기 위해, 순서가 같으면 인덱스가 작은 쪽, 즉 $\textit{lower}\,$ 구간의 데이터를 가져옵니다. 그러면 같은 순서의 데이터는 인덱스가 낮은 것이 항상 낮은 채로 유지되므로, 소팅이 스테이블하게 됩니다. (반대로 인덱스가 높은 쪽에서 먼저 가져오면 스테이블하지 않게 됩니다. 확인해보세요.)

시간 복잡도 분석

시간 복잡도를 수행한 수도코드 줄의 개수라고 합시다. 머지는 구간의 길이가 $n$이면 반복문을 $n$ 번 수행합니다. 반복문은 네 줄의 수도코드를 수행하고, 반복문 외에는 다섯 줄을 수행하므로, 머지의 시간 복잡도 $T_m(n)$은 $4n + 5$로 쓸 수 있습니다.

그렇다면 머지 소트의 시간 복잡도 $T(n)$을 구해봅시다. 머지 소트는 어떤 입력 값이든 결과적으로 똑같은 다음 점화식recurrence relation을 가집니다.

여기서 쓰인 천장 함수 혹은 실링 함수ceiling function $\lceil x \rceil$는, $\lceil 3.1 \rceil = 4$처럼 소수점이 있다면 올리기 위해 쓰였습니다. 구간을 반으로 나눈 재귀 수행 때문에, 점화식은 $T(\lceil n / 2 \rceil)$과 $T(\lfloor n / 2 \rfloor)$을 가집니다. 그리고 머지 때문에 $T_m(n)$을 가집니다. 그렇지 않고 $n \leq 1$이라면, 배열을 바로 리턴하는 부분 때문에 $T(n)=2$가 됩니다.

플로어 함수와 실링 함수가 실제로 역할을 하는 경우는, 구간의 크기 $n$이 $5$ 처럼 홀수라서 $n/2$에 소수점이 나타날 때입니다. 즉 $\lfloor 2.5 \rfloor = 2$, $\lceil 2.5 \rceil = 3$ 처럼 각각 소수점 버림과 올림을 맡습니다. 하지만 $\lceil n/2 \rceil$와 $\lfloor n/2 \rfloor$는 점화식을 풀어서 얻는 $T(n)$에 결과적으로 영향을 미치지 않습니다. 이는 수학적으로 길게 증명하기보다, $\lceil x \rceil$는 $x$와 차이가 $1$ 미만이므로 무시할만큼 작기 때문이라고 대신 설명하겠습니다. 따라서 단순히 $n/2$으로 바꾸더라도 무방합니다.

$n$이 $2, 4, 8, \dotsc$ 같은 $2^k$ 꼴이라고 가정하고, 이 점화식을 다음처럼 반복 적용하면 $T(n) = \Theta(n \lg n)$을 얻습니다.

여기서 $T(n/2)$을 $T(1)$까지 줄이기 위해 $\lg n-1$ 번 반복 적용이 필요하다는 점과, $2^kT_m(n/k)$ 꼴은 $\sim\!4n$이라는 점을 이용합니다. 앞서 언급했듯이, $n$이 $2^k$ 꼴인 경우를 보인 것이지만 일반적인 $n$의 경우에도 결과는 다르지 않습니다.

자바로 구현하기

이전 글에서 소팅 알고리즘을 스트레터지 패턴strategy pattern으로 구현하기 위해, 소팅 스트레터지 클래스가 다음 인터페이스를 구현하도록 만들었습니다.

public interface ArraySortStrategy<T> {
  public T[] sortArray(T[] arr, int begin, int end, Comparator<T> comp);
}

이는 배열 arr에서 구간 [begin, end)을 comp 오더링으로 소트함을 의미합니다.

여기서도 머지 소트를 스트레터지로 구현합시다. 앞으로 여러 방법으로 머지 소트를 만들 것이기 때문에, 먼저 추상 머지 클래스를 만듭시다.

public abstract class AbstractMergeStrategy<T>
    implements ArraySortStrategy<T> {
  // ...
}

이어서 sortArray() 메소드를 만듭시다. 머지 결과를 임시로 담을 aux 배열을 관리하고, 실제 소트는 mergeSortArray() 메소드에 맡깁니다. 소팅 알고리즘을 본격적으로 구현할 이 메소드는 서브 클래스에서 제공할 것입니다.

  private T[] aux;

  public T[] sortArray(T[] arr, int begin, int end, Comparator<T> comp) {
    this.aux = arr.clone();

    this.mergeSortArray(arr, begin, end, comp);

    this.aux = null;

    return arr;
  }

  abstract protected void mergeSortArray(T[] arr, int begin, int end,
    Comparator<T> comp);

그리고 각각의 머지 소트 구현에서 공통으로 쓸 머지는 다음과 같이 수도코드를 그대로 옮깁니다.

  protected void mergeArrays(T[] arr, int begin, int mid, int end,
      Comparator<T> comp) {
    // lower <- [lowerBegin, lowerEnd)
    int lowerBegin = begin;
    int lowerEnd = mid;
    // upper <- [upperBegin, upperEnd)
    int upperBegin = mid;
    int upperEnd = end;

    for (int i = begin; i < end; ++i) {
      if (isLessOrEqualLowerBegin(arr, lowerBegin, lowerEnd, upperBegin, upperEnd, comp)) {
        this.aux[i] = arr[lowerBegin++];
      } else {
        this.aux[i] = arr[upperBegin++];
      }
    }

    System.arraycopy(this.aux, begin, arr, begin, end-begin);
  }

구현 상의 isLessOrEqualLowerBegin() 메소드는, lower의 첫 데이터가 upper의 첫 데이터보다 낮은지 알아내는 부분으로, 수도코드 상에선 한 줄로 표현됐던 것입니다.

그런데 실제 구현은 한 쪽 구간이 비었을 가능성도 고려해야 하는데요. 그런 경우, 다른 쪽이 더 작다고 알려주고, 그렇지 않으면, 정상적으로 비교합니다.

  public static <T> boolean isLessOrEqualLowerBegin(T[] arr, int lowerBegin, int lowerEnd, int upperBegin, int upperEnd,
      Comparator<T> comp) {
    assert lowerEnd >= lowerBegin;
    assert upperBegin >= lowerEnd;
    assert upperEnd >= upperBegin;
    assert upperEnd > lowerBegin;

    if (lowerBegin == lowerEnd) {
      return false;
    }
    if (upperBegin == upperEnd) {
      return true;
    }

    return isLessThanOrEqualTo(arr[lowerBegin], arr[upperBegin], comp);
  }

한편, 두 데이터를 비교하는 isLessThanOrEqualTo() 메소드는, 이전 글처럼 유틸 메소드로 분리한 것입니다.

public class Comparators {
  // ...

  public static <T> boolean isLessThanOrEqualTo(T source, T target, Comparator<T> comparator) {
    return comparator.compare(source, target) <= 0;
  }
}

마지막으로, 머지 소트는 서브 클래스에서 수도코드를 그대로 옮겨 구현합니다.

public class TopDownMergeStrategy<T> extends AbstractMergeStrategy<T> {
  @Override
  protected void mergeSortArray(T[] arr, int begin, int end, Comparator<T> comp) {
    if (end - begin <= 1) {
      return;
    }

    int mid = begin + (end - begin) / 2;

    this.mergeSortArray(arr, begin, mid, comp);
    this.mergeSortArray(arr, mid, end, comp);
    this.mergeArrays(arr, begin, mid, end, comp);
  }
}

이렇게 만든 머지 소트 스트레터지는, JUnit 5 프레임워크를 사용한 다음 테스트 코드처럼 사용할 수 있습니다. 이전 글에서 만들어둔 별도의 ArraySorter 클래스를 통해 데이터를 소트합니다. 이 메소드에 배열과 스트레터지를 넘기면, 전체 구간을 오름차순으로 소트합니다.

  @Test
  public void testSort() {
    Integer[] toSort = { 20, 30, 10, 40 };
    Integer[] expected = { 10, 20, 30, 40 };
    ArraySortStrategy<Integer> strat = new TopDownMergeStrategy<>();

    ArraySorter.sortArray(toSort, strat);

    assertArrayEquals(expected, toSort);
  }

이 케이스는 실제로 잘 통과합니다.

소요 시간 측정

앞서 분석했던대로, 어떤 입력 값이든 $\Theta(n \lg n)$의 시간 복잡도를 가진다는 사실을 확인할 차례입니다. 다음은 이미 소트된 배열과 반대 순서로 소트된 배열을 각각 입력 값으로 했을 때 측정한 소요 시간입니다.

이 결과가 보여주듯이, 두 입력 값이 경우 대체로 이론적인 시간 복잡도 $\Theta(n \lg n)$을 따른다고 볼 수 있습니다.

크기가 작은 경우 개선하기

시간 복잡도를 분석해 얻은 $\Theta(n \lg n)$ 같은 결과는 $n$이 커짐에 따른 경향성을 보여주지만, 반대로 $n$이 작을 때는 얘기해주는 것이 없습니다. 예를 들어, 인서션 소트는 최악의 경우에 $\Theta(n^2)$의 시간이 걸리므로 $n$이 커지면 머지 소트보다 느릴 것이지만, $n$이 작을 때는 그렇게 말할 수 없습니다.

그러면 $n$이 작을 때 인서션 소트와 머지 소트의 소요 시간을 직접 측정해봅시다. 다음은 인서션 소트에서의 최선의 경우와 최악의 경우, 즉 소트된 배열과 그 반대 순서로 된 배열일 때를 각각 시나리오로 한 결과입니다.

배열이 이미 소트된 경우, 인서션 소트의 소요 시간이 더 적고, 반대로 소트된 경우, $n = 2^4 = 16$ 부근까지 그렇습니다.

그러면 배열의 크기가 작을 때 인서션 소트로 대신하면, 머지 소트의 소요 시간을 줄일 수 있지 않을까요? 이 아이디어를 이용해 머지 소트의 개선을 시도해봅시다.

인서션 소트 섞기

만약 배열의 크기 $n$이, 미리 정해놓은 크기 $k$ 이하라면, 즉 $n \leq k$이면 인서션 소트를 대신 한다고 해봅시다. 그렇다면 $\textrm{Eq.1}$에서 구했던 머지 소트의 시간 복잡도는 최악의 경우에 이렇게 바뀝니다.

여기서 $T_i(n)$은 인서션 소트의 시간 복잡도이고, 이전 글에서 분석했던 것처럼, 어떤 상수 $c$에 대해 $T_i(n) \sim cn^2 = \Theta(n^2)$ 입니다.

계산의 편의를 위해 $n = 2^s$ 꼴이고, $k = 2^t$ 꼴이라고 해도 일반성을 잃지 않을 것입니다. 앞에서 했던 대로, 점화식을 반복 적용하면 다음을 얻습니다.

여기서 $k = 1$이면 인서션 소트 없이 머지 소트만 하는 경우이고, 실제로 $T(n)$은 $\Theta(n \lg n)$가 됩니다. 반면, $k$가 $n$에 가까워지면 기존 머지 소트보다 불리한 시간 복잡도 $\Theta(n^2)$를 가진다는 사실을 알 수 있습니다. 이 경우는 처음부터 인서션 소트를 하는 것이기 때문에 그렇습니다.

따라서 $k$ 값은 낮은 숫자 중에 고르는 것이 나을 것입니다.

자바로 구현하기

앞서 인서션 소트를 대신 수행할 기준, 즉 $k$ 값을 정할 필요가 있었는데요. 여기서는 $k=7$로 하겠습니다. 이는 이론적인 의미가 있다기보다는, 곧 볼 것처럼 실제로 소요 시간에 개선을 보이기 때문에 선택한 값입니다. 이와 비슷하게, 자바의 구현인 OpenJDK의 머지 소트는 데이터가 일곱 개 미만일 때 인서션 소트로 전환합니다.

구현은 기존 머지 소트 알고리즘에 단순히 인서션 소트를 추가합니다. 여기서 인서션 소트는 이전 글에서 만들었던 InsertionStrategy 클래스를 그대로 이용합니다. 그리고 다음과 같이 크기가 작은 배열이면 대신 인서션 소트를 쓰도록 만듭시다.

public class TopDownInsMergeStrategy<T> extends AbstractMergeStrategy<T> {
  private static int THRESHOLD = 7;

  @Override
  protected void mergeSortArray(T[] arr, int begin, int end, Comparator<T> comp) {
    if (end - begin <= 1) {
      return;
    }

    // do insertion sort if small
    if (end - begin <= THRESHOLD) {
      ArraySorter.sortArray(arr, begin, end,
        new InsertionStrategy<>(), comp);
      return;
    }

    int mid = begin + (end - begin) / 2;

    this.mergeSortArray(arr, begin, mid, comp);
    this.mergeSortArray(arr, mid, end, comp);
    this.mergeArrays(arr, begin, mid, end, comp);
  }
}

이렇게 구현한 소트는 기존 머지 소트와 똑같은 테스트 케이스를 통과합니다. 또한 여전히 스테이블합니다. 인서션 소트와 머지 소트가 둘 다 스테이블하기 때문입니다.

소요 시간 측정

위와 같이 구현한 소트를 기존 머지 소트와 비교해봅시다.

인서션 소트를 섞었을 때, 최악의 경우에는 대략 10–20 퍼센트 줄어든 소요 시간을, 최선의 경우에는 20–40 퍼센트를 보여줍니다. 한편, 이렇게 줄어든 소요 시간의 폭은 $n$이 늘어날 수록 줄어듭니다. 즉 아주 큰 $n$에 적용하려고 한다면, 실제 측정을 통해 정말로 개선이 나타나는지 확인이 필요할 것입니다.

아래에서 위로 반복하기

머지 소트는 재귀를 통해 큰 배열을 작게 나누면서 소트를 진행합니다. 그런데 이전 글에서 본 것처럼, 재귀 알고리즘은 반복 알고리즘으로 바꿀 수 있는데요. 머지 소트 또한 그렇게 바꿀 수 있습니다.

머지 소트가 재귀를 통해 바꾸는 것은 소트 구간입니다. 그리고 하나에서 시작해 두 배씩 늘어난다는 것을 미리 알 수 있습니다. 그러면 소트 구간의 관리를 재귀 대신 반복문에 맡겨봅시다.

다시 말해, 재귀로 구간을 하나씩 나누는 과정 없이, 처음부터 구간의 크기를 하나로 시작해 머지합니다. 그리고 구간의 크기를 두 배씩 키우면서 머지합니다.

여기서는 구간의 크기를 $\textit{size}_\textit{\small m}$이라고 합시다. 배열을 이 크기의 구간으로 나누고, 두 개씩 고르면 머지할 구간이 됩니다. 이를 $[\textit{begin}_\textit{\small m}, \textit{mid}_\textit{\small m})$과 $[\textit{mid}_\textit{\small m}, \textit{end}_\textit{\small m})$으로 나타냅시다.

기존 머지 소트는 구간을 반으로 나누면서 재귀를 수행하므로 탑 다운top-down 방식이라고도 불립니다. 반면 반복문을 이용한 것은 크기를 늘려가므로 바텀 업bottom-up으로 불립니다. 이 방식은 이런 수도코드로 옮길 수 있습니다.

이렇게 바꾸더라도 시간 복잡도는 그대로 $\Theta(n \lg n)$이 됩니다. 바깥쪽 반복문이 대략 $\lg n$ 번 반복하고, 안쪽 반복문이 배열의 $n$ 개의 데이터에 모두 접근하기 때문입니다. 하지만 탑 다운 방식은 재귀 스택을 위해 메모리를 사용하지만, 바텀 업 방식은 그런 스택이 필요 없으므로 그만큼 메모리를 덜 쓴다는 장점이 있습니다.

자바로 구현하기

자바 코드로는 탑 다운 방식의 스트레터지를 만들어 수도코드를 그대로 옮겨 만듭니다.

public class BottomUpMergeStrategy<T> extends AbstractMergeStrategy<T> {
  @Override
  protected void mergeSortArray(T[] arr, int begin, int end, Comparator<T> comp) {
    int size = end - begin;

    for (int mergeSize = 1; mergeSize < size; mergeSize *= 2) {
      for (int mergeBegin = begin; mergeBegin < end; mergeBegin += 2*mergeSize) {
        int mergeMid = mergeBegin + mergeSize;
        if (mergeMid >= end) {
          break;
        }

        int mergeEnd = Math.min(mergeMid + mergeSize, end);

        this.mergeArrays(arr, mergeBegin, mergeMid, mergeEnd, comp);
      }
    }
  }
}

이 또한 아까와 같은 똑같은 테스트 케이스를 통과합니다.

인버전 개수 세기

인버전이란 반대 순서로 있는 두 데이터를 말합니다. 그리고 이전 글에서 계산했던 것처럼, $n$ 개의 데이터에서 인버전은 최대 $n(n-1)/2$ 개 존재합니다.

그렇다면 인버전의 개수를 세는 알고리즘은 어떻게 만들 수 있을까요? 간단히 생각해보면, 인서션 소트의 스왑 횟수 자체가 인버전 개수이므로, 인서션 소트의 스왑 횟수를 세면 될 것입니다. 그러면 이 알고리즘의 시간 복잡도는 인서션 소트처럼 최악의 경우 $\Theta(n^2)$를 가질 것입니다.

하지만 머지 소트에서도 인버전을 셀 수 있습니다. 머지 과정에서 데이터를 하나씩 가져올 때, 데이터가 인덱스가 큰 쪽에 있는 경우, 인덱스가 작은 쪽에 있는 모든 데이터와 인버전을 이룹니다. 반면, 인덱스가 작은 쪽에서 가져올 경우, 이것과 이루는 인버전은 없습니다.

따라서 인덱스가 큰 쪽에서 데이터를 가져올 때, 작은 쪽 구간의 크기를 더해나가면 인버전의 총 개수가 됩니다. 예를 들어, 다음 구현과 같이 머지하는 메소드 mergeArrays()가 numInv 변수로 인버전을 세도록 바꿔볼 수 있습니다.

  protected int mergeArrays(T[] arr, int begin, int mid, int end Comparator<T> comp) {
    int numInv = 0;

    // ...

    for (int i = begin; i < end; ++i) {
      if (isLessOrEqualLowerBegin(arr, lowerBegin, lowerEnd,
          upperBegin, upperEnd, comp)) {
        aux[i] = arr[lowerBegin++];
      } else {
        aux[i] = arr[upperBegin++];
        numInv += lowerEnd - lowerBegin;
      }
    }

    return numInv;
  }

머지 소트는 mergeArrays() 메소드가 리턴하는 개수를 전부 더하도록 바꾸면 총 인버전 개수를 셀 수 있게 됩니다. 구현을 완성하는 것은 직접 해보는 것으로 남기겠습니다.

마치며

추의 순서를 알아내는 저울 문제를 통해, 비교 횟수가 적어도 얼마나 커야하는 지를 생각해보았습니다. 이를 통해 비교 기반 소팅 알고리즘은 최악의 경우에 시간 복잡도가 $\Theta(n \lg n)$인 것이 최적이라는 결론을 내렸습니다. 그리고 머지 소트는 그런 알고리즘이었습니다.

한편, 재귀 알고리즘으로 구현한 머지 소트를 반복 알고리즘으로 바꿀 수 있었고, 두 방식을 각각 탑 다운, 바텀 업 머지 소트라고 불렀습니다. 그리고 머지 소트에 인서션 소트를 섞거나, 내츄럴 머지 소트를 구현하면서, 시간 복잡도를 개선하는 시도를 해보았습니다. 마지막으로는 머지 소트를 조금 수정해서 인버전을 세는 알고리즘으로도 만들어보았습니다.

본문의 자바 코드는 깃허브GitHub에서도 확인할 수 있습니다.

레퍼런스

• Introduction to Algorithms (3rd ed., Thomas Cormen et al., 2009)

• Algorithms (4th ed., Robert Sedgewick, 2011), 또는 알고리즘 (길벗, 2018)

• Design Patterns: Elements of Reusable Object-Oriented Software (Erich Gamma et al., 1995), 또는 GoF의 디자인 패턴: 재사용성을 지닌 객체지향 소프트웨어의 핵심요소 (프로텍미디어, 2015): 스트레터지 패턴 소개.

• The Art of Computer Programming, Vol. 3 (2nd ed., Donald Knuth, 1998), 또는 The Art of Computer Programming 3 (한빛미디어, 2008): 저울의 최소 비교 횟수 문제.

• Java Microbenchmark Harness (JMH): 자바 코드의 소요 시간 측정에 사용한 도구.

• OpenJDK Arrays.java (GitHub): 자바의 머지 소트에서 인서션 소트로 전환하는 기준 값의 예시.