외부 정렬 (External Sort)

외부 정렬 (External Sort)

정렬할 데이터가 메인 메모리에 모두 적재되지 않을 때, 보조 기억장치(디스크)를 활용하여 정렬하는 알고리즘으로, 주로 다단계 병합 정렬 사용

목적: 대용량 데이터 정렬, 메모리 한계 극복, 디스크 I/O 최적화

특징: 디스크 기반, Run 생성, 병합, I/O 최소화

2-Way 외부 병합 정렬

K-Way 병합 정렬

• •K개의 Run을 동시에 병합, 패스 수 = logK(N/M)
• •최소 힙으로 K개 중 최소 원소 선택
• •버퍼 크기 = M / (K+1)

대체 선택 (Replacement Selection)

• •힙을 사용해 평균 2M 크기의 Run 생성
• •Run 수 감소, 병합 패스 감소

다단계 병합 (Polyphase Merge)

• •불균등 Run 분배, 피보나치 수열 활용
• •테이프 드라이브 최적화

시간 복잡도: O(n log n), I/O 횟수 = O((n/B) × logM/B(n/M))

공간 복잡도: O(M) 메모리 + O(n) 디스크

장점: 대용량 데이터 정렬 가능, I/O 최적화

단점: 디스크 I/O 비용, 복잡한 구현, 순차 접근 의존

적용사례: 데이터베이스 정렬, 로그 파일 정렬, 빅데이터 처리

비교: 외부정렬(디스크/대용량) vs 내부정렬(메모리/소용량)

연관: 병합 정렬, 힙, 디스크 I/O, 데이터베이스