외부 정렬 알고리즘에서 각 런(Run)의 최적 크기는 어떻게 결정하는가?

사용 가능한 주메모리 크기와 병합 단계의 입출력 버퍼 비율로 결정한다. 런이 클수록 만들어지는 런의 개수가 줄어들어 병합 횟수가 감소한다.

도식은 주메모리를 정렬 공간과 입출력 공간으로 나누어 쓰는 구조를 나타낸다. 메모리가 허용하는 한 런을 크게 만들어 임시 파일 수를 줄인다. 대체 선택 기법을 쓰면 메모리 용량의 두 배까지 런 크기를 늘린다.

런이 크면 병합할 파일이 줄어들어 디스크 탐색 시간을 아낀다. 하지만 병합할 런이 늘어날수록 각 런에 할당하는 입출력 버퍼가 작아진다. 버퍼가 작아지면 디스크 접근 횟수가 다시 늘어난다.

디스크 블록 입출력 단위와 k-way 병합에 필요한 버퍼 공간의 균형점에서 최적 크기가 정해진다.