외부정렬

특징

1.입력 크기가 매우 커서 읽고 쓰는 시간이 오래 걸리는 보조 기억 장치에 입력을 저장할 수 밖에 없는 상태에서 수행되는정렬.

2.내부정렬과 반대되는 알고리즘.( 대부분의 알고리즘이 내부정렬)

---

ExternalSort 슈도코드

입력: 입력 데이터에 저장된 입력 HDD

출력: 정렬된 데이터가 저장된 출력 HDD

1  입력 HDD에 저장된 입력을 크기가 M만큼씩 주기억 장치에 읽어들인 후 내부정렬 알고리즘으로 정렬하여

    별도의 HDD에 저장한다. 다음 단계에서 별도의 HDD는 입력 HDD로 사용되고, 입력 HDD는 출력 HDD로 사용된다.

2  while ( 입력 HDD에 저장된 블록 수 > 1) {

3       입력 HDD에 저장된 블록을 2개씩 선택하여, 각각의 블록으로부터 데이터를 부분적으로 주기억 장치에 읽어 들여서           합병을 수행한다. 이때 합병된 결과는 출력 HDD에 저장한다. 단, 입력 HDD에 저장된 블록 수가 홀수일 때에는

         마지막 블록은 그대로 추력 HDD에 저장한다.

4      입력과 출력 HDD의 역할을 바꾼다.

        }

5  return 출력 HDD