[Algorithm] 외부 정렬 알고리즘(external sorting algorithm)

---

외부 정렬 (External Sort)

 

메인 메모리(main memory)인 램에 전체 데이터를 올릴 수 없다면 보조 메모리(auxiliary memory)인 하드 디스크, SSD 등에서 일부 데이터만을 메인 메모리에 가져와 정렬해야 한다. 이를 외부 정렬이라 한다. 앞으로 메인 메모리는 메모리, 보조 메모리는 디스크라 하겠다. 일부 데이터만을 가져올 수 있기 때문에 한 번에 데이터 정렬이 불가능하고, 여러번 메모리와 디스크를 오가며 정렬해야 하고, 따라서 이 경우 비교 횟수 보다는 읽고 쓰는 시간, 즉 I/O 횟수가 더 중요하게 작용한다. 따라서 외부 정렬에서 시간복잡도 기준은 I/O 횟수이다.

외부 정렬을 앞서 말한대로 외부에서 데이터를 불러와서 정렬하는 정렬 단계(sort phase)와 이를 다시 합치는 병합 단계(merge phase)로 나뉜다. 정렬 단계에서는 데이터를 메모리에 올릴 수 있는 블록(block) 단위로 잘라서 읽는다. 내부 정렬로 각 블록을 정렬한 후 디스크에 다시 저장한다. 이렇게 만들어진 블록을 런(run)이라 한다. 병합 단계에서는 정렬 단계에서 만들어진 런(run)들을 병합하는데, 이 과정을 반복함으로써 하나의 정렬된 전체 데이터를 얻는다.

 

---

균형적 다방향 합병 정렬 (Balanced Multiway Merge Sort)

 

여러 개의 디스크를 사용하여 동시에 여러 런(run)을 병합하는 방법으로 외부 정렬을 수행한다. 예를 들어 총 $ 4 $ 개의 디스크가 있다면 입력 디스크 $ 3 $ 개와 출력 디스크 $ 1 $ 개로 활용하여 한 번에 $ 3 $ 개의 정렬된 블록을 병합하는 것이다.

정렬 순서는 다음과 같다. 먼저 메모리에서 정렬된 작은 런(run)들을 여러 개 생성하고, 각 디스크에 런(run)을 균등(balanced)하게 배분한다. 출력 디스크에 병합된 결과를 출력하면 병합된 블록의 수 자체는 점점 줄어들 것이다. 출력 디스크는 병합이 끝나면 다시 입력 디스크로 사용되며 역할을 순환한다. 반복하면 병합이 끝난다.

예를 들어 전체 데이터가 $2$GB이고, 메모리가 $1$GB라고 하자. 그렇다면 데이터 절반씩 가져와 정렬하고 이를 다시 디스크에 순서대로 저장한다. 그렇다면 디스크에는 2개의 런(run)이 만들어진다. 이제 2개의 런에서 작은 값부터 차례로 가져와 비교하고 더 작은 값을 디스크에 저장하고, 빈 공간은 다시 처음 런에서 가져와 채우고, 다시 비교하고를 반복해서 병합한다. 병합이 끝난다면 전체 데이터는 정렬된 상태가 된다.

데이터 수를 $ n $, 메모리 크기를 $ b $, 디스크 개수를 $ t $ 라 할 때 I/O 기준 시간복잡도는 다음과 같다.

$$ \left\lceil \log_{t/2} \frac{n}{b} \right\rceil + 1 $$

 

---

대체 선택 (Replacement Selection)

 

정렬된 런(run)을 만들 때 최소힙(min heap)을 이용해 평균적으로 더 큰 런(run)을 생성하는 방식이다.

아이디어는 다음과 같다. 메인 메모리에 데이터를 불러오고 최소힙으로 정렬하여 가장 작은 값을 디스크에 출력한다. 다시 데이터를 하나 가져온다. 이 때 가져온 값이 방금 전에 디스크에 출력한 값보다 작은지 확인한다. 작다면 다시 최소힙으로 만들고 처음 출력한 디스크에 차례로 출력하면 된다. 만약 크다면 방금 입력받은 값을 마킹(frozen)하여 메인 메모리에서 나가지 못하도록 한다. 이를 반복하다가 메인 메모리에 모든 값이 마킹되었다면 지금까지 디스크에 출력한 값들로 런(run)을 만들고, 새로운 런을 다시 만든다.

이 방식을 활용하면 평균적으로 큰 런(run)을 생성할 수 있기 때문에 병합 단계가 줄어든다. 평균적으로 런(run)의 크기는 메모리의 크기를 $ b $ 라 할 때 $ 2b $ 이다. 앞에서 균형적 다방향 합병 정렬을 통해서는 처음 런(run)을 만들 때 크기가 $ b $ 였기 때문에 이와 비교하면 더 효율적이다.

 

---

다단계 합병 정렬 (Polyphase Merge Sort)

 

디스크 수에 따라 처음 런(run)을 만들 때 그 수를 분배하는 방식을 피보나치 수열과 유사하게 만드는 방법이다. 이렇게 하면 비표율적인 I/O가 제거되어 더 효율적인 외부 정렬이 가능해진다.

비효율적인 I/O가 무엇인지 생각해보기 위해 앞서 언급한 균형적 다방향 합병 정렬을 생각해보자. 메모리 크기가 $ b $ 라 할 때 총 데이터가 $ 8 b $ 이고, 총 디스크가 $ 5 $ 개라고 가정해보자. 그렇다면 먼저 메모리 크기에 맞게 $ 8 $ 개의 런(run)이 만들어지고, 이를 출력 디스크 하나를 제외한 $ 4 $ 개의 디스크에 각각 $ 2 $ 개의 런(run) 씩 분배할 것이다. 이를 병합하기 위해 런을 가져와 출력 디스크로 쓰면서 병합하고, 출력 디스크는 다시 이를 원래 디스크로 복사한다. 이를 반복하여 다시 출력 디스크를 제외한 디스크들에 균형적으로 병합된 런을 분배한다. 이 과정에서 병합할 때 출력 디스크로 쓰고, 이를 다시 출력 디스크가 아닌 디스크로 옮기는 과정이 포함되었고, 이때문에 비효율적인 I/O가 발생한다. 

다단계 합병 정렬은 이를 피보나치 수열과 유사한 형태로 디스크에 각 블록, 즉 런(run)을 분배하여 해결한다. 총 디스크가 $ 5 $ 개 라고 가정해보자. 그럼 역으로 생각했을 때 최종적으로 하나의 디스크에 정렬된 데이터, 즉 단일 블록이 들어가있고, 나머지 디스크는 비어있을 것이다. 그럼 그 전 단계에서는 어떤 경우에 가장 효율적으로 많은 블록이 병합될 수 있을까 생각해보면, 최종적으로 정렬된 데이터가 들어가는 디스크를 제외한 모든 디스크에 하나씩 블록이 들어가 있고, 이를 메모리가 병합하여 최종 디스크에 쓰는 경우가 가장 효율적일 것이다. 만약 블록이 하나라도 더 많다면 다시 한번 병합을 해야하고, 하나라도 더 적다면 놀고 있는 디스크가 있다는 의미이기 때문이다. 그럼 또 다시 이 경우에서 역으로 생각해보자. 하나의 디스크는 출력을 위해 비워놓는다고 하더라도 각 들어있는 블록의 수가 $ 0, 1, 1, 1, 1 $ 인 경우에 그 전 단계는 어떻게 블록이 들어있었어야 효율적이었을까. 하나의 디스크는 역시 출력 디스크여야하기 때문에 비워둔다고 하면 $ 0, 1, 1+1, 1+1+0, 1+1+0+0 $ 일 것이다. 이를 반복하면 아래와 같이 표를 채울 수 있다. $ T $ 는 디스크이고, 열은 각 단계로 $ 0 $ 이 마지막 정렬이 완료된 단계이다.

	6	5	4	3	2	1	0
$$ T_0 $$	$$0$$	$$15$$	$$7$$	$$3$$	$$1$$	$$0$$	$$1$$
$$ T_1 $$	$$29$$	$$14$$	$$6$$	$$2$$	$$0$$	$$1$$	$$0$$
$$ T_2 $$	$$27$$	$$12$$	$$4$$	$$0$$	$$2$$	$$1$$	$$0$$
$$ T_3 $$	$$23$$	$$8$$	$$0$$	$$4$$	$$2$$	$$1$$	$$0$$
$$ T_4 $$	$$15$$	$$0$$	$$8$$	$$4$$	$$2$$	$$1$$	$$0$$

특정 패턴을 따르는 것인데 $ 0,0,0, 1, 1, 2, 4, 8, 15, \cdots $ 와 같은 패턴을 볼 수 있다. $ 0, 0, 0, 1 $ 에서 디스크 숫자인 $ 4 $ 개씩 더한 값을 추가하여 수열을 만든 것으로 피보나치 수열과 유사한 패턴이다. 그리고 출력용으로 비워두는 디스크 전 디스크는 각 단계별로 커지고, 거기서 왼쪽으로 하나씩 더해가며 커진다. 아래와 같은 식이다.

$$ \begin{aligned} &0\quad 0\quad 0\quad \underline{1} \\ &\phantom{0}\quad \phantom{0}\quad \underline{\phantom{0}\quad \phantom{1}} \\ &\phantom{0}\quad \underline{\phantom{0}\quad \phantom{0}\quad \phantom{1}} \\ &\underline{\phantom{0}\quad \phantom{0}\quad \phantom{0}\quad \phantom{1}} \end{aligned} $$

수를 나타내면 아래와 같은데, 위와 같이 차례대로 수를 더해주며 쓰면 된다.

$$ \begin{aligned} &0\quad 0\quad 0\quad 1\quad 1\quad 2\quad 4\quad 8\quad 15\quad \cdots \end{aligned} $$

결과적으로 각 단계에서 각 디스크의 블록을 모두 더해서 총 블록을 구한다음 필요한 블록에 도달하면 그 부분부터 병합을 진행하면 된다. 필요한 블록은 전체 데이터를 메모리 크기로 나누면 구할 수 있다.

디스크가 적은 경우에는, 즉 $ 3 $ 개만 사용하는 경우에는 균형적 다방향 합병 정렬이 다단계 합병 정렬보다 효율적이다. 그러나 디스크 수가 많아진다면 다단계 합병 정렬이 더 효율적이 된다. 예를 들어서 디스크 수가 $ 5 $ 개 일 때 균형적 다방향 합병 정렬은 $ \log_{5/2} n + 1 $ 회 병합되는데, 다단계 합병 정렬은 약 $ 0.7 \times \log_2 n + 1 $ 회 병합한다.