외부정렬

입력 크기가 매우 커서 읽고 쓰는 시간이 오래 걸리는 보조 기억 장치(디스크, 테이프 등)에 입력을 저장할 수 밖에 없는 상태에서 수행되는 정렬

주 기억 장치의 용량 만큼 보조기억장치에서 데이터를 읽어 정렬한다

보조기억장치의 특성에 따라서는 데이터에 순차적 접근만 가능하다

보조기억장치와 주기억장치 사이에 데이터 이동 횟수는 최소화를 해줘야 한다.

C.f. 보조기억장치는 접근속도가 느리고, 접근이 제한적이다.

레코드 접근시간 >> 레코드 비교시간

Ex)

• 컴퓨터의 주기억 장치의 용량이 1GB이고, 정렬할 입력의 크기가 100GB ⇒ 내부정렬 알고리즘으로 정렬할 수 없다.
• 외부 정렬은 입력을 분할해서 주기억 장치에서 수용할 만큼의 데이터에 대해서만 내부정렬을 수행 → 그 결과를 보조 기억 장치에 저장
• 100GB의 데이터를 1GB만큼씩 주기억 장치로 읽어 들이고, 퀵 정렬과 같은 내부정렬 알고리즘을 이용하여 정렬한 후, 다른 보조 기억 장치에 저장한다.
• 이것을 반복하면 원래의 입력 100GB가 100개씩 정렬된 블록으로 분할되어 보조 기억 장치에 저장된다.

• 그 다음 정렬된 블록들을 하나의 정렬된 거대학 블록으로 만들어야하기에 합병을 반복 수행한다(merge)

  = 블록들을 부분적으로 주기억장치에 읽어들여 합병을 수행하고 부분적으로 보조 기억 장치에 쓰는 과정

  Ex) 1GB 블록 2개가 2GB 블록 한개로 합병될 때

  

https://dudri63.github.io/2019/02/03/algo32/

• 나머지 98개 블록 대해 위 과정 49회 반복하면 2GB블록 50개가 만들어짐
• 이후에는 또 2GB 블록 두개씩 merge하는 과정 25회
• →반복....→ 블록크기가 2배씩 커지면서 블록수는 1/2이 되어 마지막엔 100GB블록 하나가 된다.

런(run)

하나의 파일을 여러 개의 서브파일(subfile)로 나눠 내부 정렬 기법을 사용해 정렬시킨 파일

ex) 2000개의 레코드를 가진 파일을 정렬하는 문제에서 주기억장치의 용량이 1000개의 레코드까지만 허용한다면, 2개의 런이 사용된다.