외부 정렬 — 메모리에 안 들어가는 데이터를 정렬하는 법

원본 파일: [38, 27, 43, 3, 9, 82, 10, 44, 15, 58, 21, 7]
메모리: 4개씩 처리 가능

Run 1: [3, 27, 38, 43]    (38,27,43,3을 메모리에서 정렬)
Run 2: [9, 10, 44, 82]    (9,82,10,44를 메모리에서 정렬)
Run 3: [7, 15, 21, 58]    (15,58,21,7을 메모리에서 정렬)

1차 병합:
  Run 1 + Run 2 → [3, 9, 10, 27, 38, 43, 44, 82]
  Run 3 → [7, 15, 21, 58]                          (대기)

2차 병합:
  [3, 9, 10, 27, 38, 43, 44, 82] + [7, 15, 21, 58]
  → [3, 7, 9, 10, 15, 21, 27, 38, 43, 44, 58, 82]

public class ExternalSort {

    // Phase 1: 정렬된 런(run) 파일 생성
    public static List<File> createSortedRuns(File inputFile, int chunkSize)
            throws IOException {
        List<File> runs = new ArrayList<>();
        BufferedReader reader = new BufferedReader(new FileReader(inputFile));

        List<Integer> chunk = new ArrayList<>();
        String line;

        while ((line = reader.readLine()) != null) {
            chunk.add(Integer.parseInt(line.trim()));

            if (chunk.size() >= chunkSize) {
                runs.add(writeSortedRun(chunk));
                chunk.clear();
            }
        }

        if (!chunk.isEmpty()) {
            runs.add(writeSortedRun(chunk));
        }
        reader.close();
        return runs;
    }

    private static File writeSortedRun(List<Integer> chunk) throws IOException {
        Collections.sort(chunk); // 메모리 내 정렬

        File runFile = File.createTempFile("run_", ".txt");
        BufferedWriter writer = new BufferedWriter(new FileWriter(runFile));
        for (int val : chunk) {
            writer.write(val + "\n");
        }
        writer.close();
        return runFile;
    }

    // Phase 2: K-Way Merge
    public static void kWayMerge(List<File> runs, File outputFile)
            throws IOException {
        // min-heap: (값, 런 인덱스)
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            Comparator.comparingInt(a -> a[0])
        );

        BufferedReader[] readers = new BufferedReader[runs.size()];
        BufferedWriter writer = new BufferedWriter(new FileWriter(outputFile));

        // 각 런의 첫 원소를 힙에 삽입
        for (int i = 0; i < runs.size(); i++) {
            readers[i] = new BufferedReader(new FileReader(runs.get(i)));
            String line = readers[i].readLine();
            if (line != null) {
                minHeap.offer(new int[]{Integer.parseInt(line.trim()), i});
            }
        }

        // 병합
        while (!minHeap.isEmpty()) {
            int[] min = minHeap.poll();
            writer.write(min[0] + "\n");

            // 해당 런에서 다음 원소 읽기
            String line = readers[min[1]].readLine();
            if (line != null) {
                minHeap.offer(new int[]{Integer.parseInt(line.trim()), min[1]});
            }
        }

        writer.close();
        for (BufferedReader r : readers) r.close();

        // 임시 파일 정리
        for (File run : runs) run.delete();
    }
}

런 수: R
한 번에 병합하는 런 수: K

패스 횟수 = ⌈log_K(R)⌉

예: 런 1000개, K=100 → 패스 2번 (100개씩 → 10개 → 1개)

// 개념: 힙에서 최솟값을 출력하고, 새 원소가 출력된 값보다 크면 힙에 추가
// 작으면 다음 런으로 넘김
// 평균적으로 메모리 크기의 2배인 런이 생성됨

// 입력 버퍼: 각 런에 대해 블록 단위로 읽기
// 출력 버퍼: 결과를 블록 단위로 쓰기
// 버퍼 크기 = 가용 메모리 / (K + 1)
//   K개 입력 버퍼 + 1개 출력 버퍼

-- EXPLAIN으로 filesort 확인
EXPLAIN SELECT * FROM orders ORDER BY total_price;
-- Extra: Using filesort

-- sort_buffer_size 확인
SHOW VARIABLES LIKE 'sort_buffer_size';
-- 기본값: 256KB ~ 수 MB

Map 출력 → 파티셔닝 → 각 파티션 내 정렬 → Reduce로 전달
                        ↑ 외부 정렬

# Unix의 sort 명령어도 외부 정렬을 사용
sort --buffer-size=2G --temporary-directory=/tmp bigfile.log

public class SimpleExternalSort {
    private static final int CHUNK_SIZE = 100_000; // 메모리에 올릴 수 있는 원소 수

    public static void sort(String inputPath, String outputPath) throws IOException {
        // Phase 1: 정렬된 런 생성
        List<File> runs = createSortedRuns(new File(inputPath), CHUNK_SIZE);

        // Phase 2: K-Way Merge
        kWayMerge(runs, new File(outputPath));
    }

    public static void main(String[] args) throws IOException {
        sort("large_data.txt", "sorted_data.txt");
    }
}