메모리에 다 들어가지 않는 큰 파일을 정렬하려 합니다. 병합 정렬은 어떻게 활용할 수 있나요?

메모리에 전체 파일을 올릴 수 없다면, 메모리에 들어오는 크기만큼 읽어 정렬한 임시 파일을 여러 개 만들고, 이 정렬된 run들을 병합해 최종 파일을 만듭니다. 병합 단계에서는 각 run의 현재 맨 앞 레코드만 비교하므로 전체 데이터가 메모리에 동시에 있을 필요가 없습니다. 이 방식을 외부 정렬(external sorting)이라고 부릅니다.

병합 I/O와 실패 복구를 설계합니다

먼저 메모리 버퍼가 가득 찰 때까지 레코드를 읽고 키로 정렬한 뒤 임시 파일에 순서대로 씁니다. 다음 묶음을 반복해 각 run 내부의 정렬을 보장합니다. 이후 각 파일의 앞 레코드를 읽어 최소 힙에 (키, run 번호, 버퍼 위치)로 넣고, 가장 작은 레코드를 출력한 뒤 그 run에서 다음 레코드를 읽습니다. 이 과정은 한 번에 한 레코드만 비교하므로 메모리는 run 수와 버퍼 크기에 의해 제한됩니다. 이를 k-way merge(다중-way 병합)라고 합니다.

동시에 열 수 있는 파일 핸들·버퍼 메모리가 제한되면 모든 run을 한 번에 병합할 수 없습니다. fan-in을 낮춰 여러 단계로 병합하면 임시 파일과 디스크 읽기·쓰기가 늘어납니다. fan-in을 높이면 병합 단계는 줄지만 각 파일에 버퍼를 나눠야 하고 작은 버퍼로 인해 I/O가 잘게 쪼개질 수 있습니다. 순차 읽기·쓰기와 충분한 버퍼를 사용해 디스크 탐색과 시스템 호출 횟수를 줄이겠습니다.

정확성과 실패 복구를 설계합니다

동일 키의 원래 순서를 보존해야 한다면 입력 순번을 보조 키로 함께 저장하거나, 병합 시 run 번호와 run 내부 순서를 명확히 비교해야 합니다. 단순히 키만 비교하면 run 생성 순서가 안정성 규칙과 맞지 않을 수 있습니다. 중간 단계가 실패해도 완성되지 않은 파일을 최종 결과로 노출하지 않도록 임시 이름과 원자적 교체를 사용하고, run 목록과 체크섬을 기록해 재개 가능성을 정합니다.

검증은 메모리 상한, 빈 파일, 모든 동점, 매우 긴 레코드, 디스크 부족, 중단 후 재개를 포함합니다. CPU 비교 횟수보다 총 디스크 읽기·쓰기와 임시 공간이 지배적일 수 있으므로 함께 측정합니다. 이미 정렬된 입력 구간을 감지하는 것은 run 수를 줄일 수 있지만, 감지 비용과 구현 복잡성을 실제 I/O 이득과 비교하겠습니다.

외부 정렬은 메모리에 들어오는 크기별 run을 만들고, 각 run의 앞 원소만 비교해 최종 파일로 병합합니다. k-way 병합에서 힙에는 각 run의 현재 레코드 하나만 두고 하나를 출력할 때 그 run의 다음 레코드를 채웁니다. fan-in을 높이면 병합 단계와 디스크 왕복은 줄지만 파일별 버퍼가 작아지고 동시에 열 파일 수가 늘어납니다.

동일 키의 안정성을 보장하려면 원본 순번을 보조 키로 저장해야 run 경계를 넘어도 순서가 유지됩니다. 키와 오프셋만 정렬하면 레코드 이동은 줄지만 최종 랜덤 읽기가 커질 수 있습니다. 중단된 임시 파일을 최종 결과로 노출하지 않도록 run의 레코드 수·체크섬·완료 표식을 기록하고, 메모리·디스크 상한과 빈 파일·디스크 부족을 기준 구현과 비교하겠습니다.

입력 1TB를 1GB짜리 정렬 run 약 1,000개로 만든 뒤 한 번에 32개씩 병합한다면 대략 두 단계의 병합이 필요합니다. 각 단계에서 데이터 전체를 읽고 쓰므로 임시 디스크와 총 I/O가 큽니다. 입력·출력 버퍼, 힙 레코드, 디코딩 메모리도 1GB 예산에 포함해야 하며 레코드 하나가 버퍼보다 큰 경우의 처리도 정해야 합니다.