| 외부정렬 | 균형적다방향머지정렬 |

■ 균형적 다방향 머지 정렬(balanced multiway merge sort) 개념

• 외부 정렬 알고리즘은 머지 정렬을 응용/변형하여 만들 수 있는데 그러한 종류의 알고리즘 중의 하나인 간단하면서도 기본적인 알고리즘

• 테이프에 저장되어 있는 자료들을 주기억장치에 옮겨올 수 있도록 작은 블록으로 나눔

• 나누어진 블록들은 각각 주기억장치에서 정렬된 후에 다시 여러 개의 테이프에 분산되어 저장

• 이 작은 정렬된 블록들은 주기억장치와 여러 테이프 사이를 오고가며서 두 개씩 짝지어 머지

• 머지 과정이 순환적으로 반복되면서 블록의 수가 줄고 블록의 크기가 커지게 됨

• 한 개의 블록만이 남게되면 정렬이 완료

• 이 정렬은 여러 단계에 걸쳐서 여러 개의 테이프에 분산되어 있는 블록들을 머지하므로 다방향 머지 정렬이라고 함