java 74 lines · 10 steps

External merge sort in Java

Sort a file too big for memory by splitting it into sorted chunks and k-way merging them with a heap.

Explained by highlit
Advanced external-sort merge-sort priority-queue file-io streaming
1public final class ChunkSorter {
2 
3 private static final int MAX_LINES_PER_CHUNK = 100_000;
4 
5 public Path sort(Path input, Path output, Path tempDir) throws IOException {
6 List<Path> chunks = split(input, tempDir);
7 try {
8 merge(chunks, output);
9 } finally {
10 for (Path chunk : chunks) {
11 Files.deleteIfExists(chunk);
12 }
13 }
14 return output;
15 }
16 
17 private List<Path> split(Path input, Path tempDir) throws IOException {
18 List<Path> chunks = new ArrayList<>();
19 try (BufferedReader reader = Files.newBufferedReader(input)) {
20 List<String> buffer = new ArrayList<>(MAX_LINES_PER_CHUNK);
21 String line;
22 while ((line = reader.readLine()) != null) {
23 buffer.add(line);
24 if (buffer.size() >= MAX_LINES_PER_CHUNK) {
25 chunks.add(flush(buffer, tempDir));
26 }
27 }
28 if (!buffer.isEmpty()) {
29 chunks.add(flush(buffer, tempDir));
30 }
31 }
32 return chunks;
33 }
34 
35 private Path flush(List<String> buffer, Path tempDir) throws IOException {
36 Collections.sort(buffer);
37 Path chunk = Files.createTempFile(tempDir, "chunk-", ".txt");
38 Files.write(chunk, buffer);
39 buffer.clear();
40 return chunk;
41 }
42 
43 private void merge(List<Path> chunks, Path output) throws IOException {
44 List<BufferedReader> readers = new ArrayList<>(chunks.size());
45 PriorityQueue<Cursor> heap = new PriorityQueue<>(Comparator.comparing(c -> c.value));
46 try {
47 for (Path chunk : chunks) {
48 BufferedReader reader = Files.newBufferedReader(chunk);
49 readers.add(reader);
50 String first = reader.readLine();
51 if (first != null) {
52 heap.add(new Cursor(reader, first));
53 }
54 }
55 try (BufferedWriter writer = Files.newBufferedWriter(output)) {
56 while (!heap.isEmpty()) {
57 Cursor cursor = heap.poll();
58 writer.write(cursor.value);
59 writer.newLine();
60 String next = cursor.reader.readLine();
61 if (next != null) {
62 heap.add(new Cursor(cursor.reader, next));
63 }
64 }
65 }
66 } finally {
67 for (BufferedReader reader : readers) {
68 reader.close();
69 }
70 }
71 }
72 
73 private record Cursor(BufferedReader reader, String value) {}
74}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1External sorting bounds memory by chunk size, letting you sort inputs far larger than RAM.
  2. 2A min-heap over one cursor per chunk performs a k-way merge in O(n log k) time.
  3. 3Wrapping cleanup in finally guarantees temp files and readers are released even when sorting fails.

Related explainers

java 
@Component
@Converter
public class EncryptedStringConverter implements AttributeConverter<String, String> {
 

Transparent column encryption in Spring & JPA

encryption aes-gcm jpa-converter
Advanced 10 steps
java 
package com.acme.billing.config;
 
import org.springframework.boot.autoconfigure.condition.ConditionalOnProperty;
import org.springframework.boot.context.properties.ConfigurationProperties;

Feature-flagged beans with Spring @ConditionalOnProperty

feature-flags conditional-beans strategy-pattern
Intermediate 5 steps
python 
import random
from typing import Iterator, List
 
 

How reservoir sampling picks k items

reservoir-sampling streaming randomness
Intermediate 5 steps
java 
public static Map<String, String> parseCookieHeader(String header) {
    Map<String, String> cookies = new LinkedHashMap<>();
    if (header == null || header.isBlank()) {
        return cookies;

Parsing an HTTP Cookie header in Java

string-parsing http url-decoding
Intermediate 6 steps
java 
public class TimedSocketReader {
 
    private static final int READ_TIMEOUT_MS = 5_000;
    private static final int CONNECT_TIMEOUT_MS = 3_000;

Reading a socket with connect and read timeouts

sockets timeouts io
Intermediate 8 steps
java 
public final class EncodingDetector {
 
    public enum Encoding {
        UTF_8, UTF_16LE, UTF_16BE, UTF_32LE, UTF_32BE, ASCII, UNKNOWN

Detecting text encoding from raw bytes in Java

byte-manipulation encoding-detection bitwise-operations
Intermediate 8 steps

Share this explainer

Here's the card — post it anywhere.

External merge sort in Java — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code