외부 정렬

• 내부정렬: 입력이 주기억 장치(내부 메모리)에 있는 상태에서 정렬이 수행되는 정렬
• 외부정렬
  • 입력 크기가 매우 커서 읽고 쓰는 시간이 오래 걸리는 보조 기억 장치에 입력을 저장할 수밖에 없는 상태에서 수행되는 정렬
  • 주기억 장치의 용량이 1GB이고, 입력 크기가 100GB라면, 어떤 내부 정렬 알고리즘이라도 직접 정렬 불가

1. 주 기억 장치에 수용할 만큼 Read/Sort

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

2. 정렬된 블록의 합병

• 정렬된 블록들을 반복적인 합병(merge)을 통해서 하나의 정렬된 거대한(100GB크기의) 블록으로 만듦
  • 블록들을 부분적으로 주 기억 장치에 읽어 들여서, 합병을 수행하여 부분적으로 보조 기억 장치에 쓰는 과정을 반복
• 블록을 부분적으로 읽어 들인 상황을 그림으로 표현
  

2.1. 1GB 블록 2개가 합병되는 과정

• 2개의 블럭이 1개로 합병
• 100개의 블럭을 대상으로 반복한다면 50개로 합병

2.2. 반복

• 이를 블록이 한 개가 될때까지 반복
• 보조 기억 장치에서 읽고 쓰기를 최소화하는 것이 중요

3. 시간복잡도

• 외부 정렬은 전체 데이터를 몇 번 처리하는가를 가지고 시간 복잡도를 측정
• 입력의 크기: N, 메모리의 크기 M
• 2^k*M = N
• k는 while-루프가 수행된 횟수
• 2^k = N/M
• k = log(N/M)
• 최종 시간복잡도는 O(log(N/M))