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

■ 외부 정렬 개념

• 정렬할 자료의 양이 적어서 자료 전체가 주기억장치에 저장될 수 있는 경우에는 내부 정렬을 사용하여 자료를 정렬함

• 자료의 양이 많을 때는 속도가 느리고 접근 방식이 제한적인 보조 기억장치에 전체 자료를 두고 자료의 일부분을 한번에 조금씩 주기억장치에 옮겨와서 정렬을 하게 되는데 이러한 종류의 정렬 알고리즘들을 외부 정렬(external sort)이라고 함

• 자료가 주기억장치와 보조 기억장치 사이를 오고가는 데 드는 시간은 주기억장치에 저장되어 있는 자료들을 서로 비교하는 데 드는 시간보다 상대가 안될 정도로 길다.

• 보조 기억장치에 있는 키를 읽거나 쓰는 횟수가 외부 정렬의 실행 시간을 결정하는 주요인이므로 이를 줄이는 방향으로 외부 정렬 알고리즘을 고안해야 함

• 외부 정렬은 머지 정렬의 머지 알고리즘을 응용하여 사용

• 주기억장치는 M개의 데이터만 정렬 가능(정렬된 데이터=run)