A first-cut implementation of this problem typically looks like:
A first-cut implementation of this problem typically looks like:
mapfile -t lines < "$input" # 1
printf '%s\n' "${lines[@]}" | sort | uniq # 2,3,4
It fails the stated requirements for six distinct reasons:
mapfile, $(cat file), or a while read loop that appends to an array keeps the entire input (and its bash string copies) in RAM. A 10 GB input cannot be sorted under a hard ceiling.read truncates at NUL, and printf '%s' then emits a shortened record. Any merge that moves records through shell variables silently corrupts data.$(...) strips all trailing newlines; echo may interpret backslashes; read without -r mangles backslashes; read leaves \r attached while surrounding tooling may strip it. Line endings and final-newline state are not preserved.LC_ALL=C, sort uses the host collation, so results are not byte-deterministic and differ across machines/locales.sort's last-resort whole-line comparison (or by an unstable internal merge), so equal-key records are reordered. -u then keeps an arbitrary representative instead of the first.EMFILE; sort -u on unsorted input re-sorts and is neither a bounded merge nor a stable collapse.The fix is to (a) never let a record byte enter a shell variable, (b) tag each record with its 1-based position as a unique secondary key, (c) sort bounded runs and merge them with a bounded fan-in k-way merge, and (d) strip the tag and collapse duplicates with a stable streaming uniq.
Save as extsort.sh (bash 4+, coreutils). It uses only cat, split, sort, cut, uniq.
#!/usr/bin/env bash
# extsort.sh -- bounded-memory, stable external merge sort (bash + coreutils)
#
# Usage: extsort.sh [INPUT] [OUTPUT]
# INPUT defaults to "-" (stdin); OUTPUT defaults to "-" (stdout)
#
# Tunables (environment):
# RUN_BYTES approx max bytes per sorted run (default 64 MiB) [split -C]
# RUN_LINES if > 0, max *lines* per sorted run (overrides RUN_BYTES)
# FANIN max inputs merged at once; >= 2 (default 8)
# DEDUP 1 = collapse exact duplicates, 0 = keep all (default 1)
# KEEP_TMP 1 = keep the work directory for inspection (default 0)
# SORT_KEY optional primary-key spec in `sort -k` syntax evaluated on the
# TAGGED line: field 1 is the position tag, body starts at field 2.
# Default whole record (-k2). Example: SORT_KEY='-k2.1,2.1'.
#
# Guarantees:
# * LC_ALL=C byte ordering; records are LF-delimited, CR/NUL are data bytes.
# * Stable: each record carries its original position as a unique secondary
# key, so output is a deterministic total order.
# * Bounded memory: one run is sorted at a time; merges stream with fan-in.
# * No record byte ever passes through a shell variable (NUL/CR safe).
set -euo pipefail
TAB=$'\t'
RUN_BYTES=${RUN_BYTES:-67108864}
RUN_LINES=${RUN_LINES:-0}
FANIN=${FANIN:-8}
DEDUP=${DEDUP:-1}
KEEP_TMP=${KEEP_TMP:-0}
IN=${1:--}
OUT=${2:--}
if ! [[ "$FANIN" =~ ^[0-9]+$ ]] || [ "$FANIN" -lt 2 ]; then
echo "extsort: FANIN must be an integer >= 2 (got '$FANIN')" >&2
exit 2
fi
WORK=$(mktemp -d "${TMPDIR:-/tmp}/extsort.XXXXXX")
cleanup() { [ "$KEEP_TMP" = 1 ] && { echo "extsort: workdir=$WORK" >&2; return 0; }; rm -rf "$WORK"; }
trap cleanup EXIT
# Phase 0: tag every record with its 1-based original position.
# `cat -n` emits "<6-wide number>\t<record>" and is byte-transparent, so NUL
# and CR inside the record survive verbatim. The tag in field 1 is the
# explicit tie-break that makes the result stable and deterministic.
TAGGED="$WORK/tagged"
if [ "$IN" = "-" ]; then
cat -n > "$TAGGED"
else
cat -n -- "$IN" > "$TAGGED"
fi
# Phase 1: cut the tagged stream into run files of bounded size.
# split -C (--line-bytes) never splits a record in half.
if [ "$RUN_LINES" -gt 0 ]; then
split -l "$RUN_LINES" -d -a 6 --additional-suffix=.run "$TAGGED" "$WORK/r."
else
split -C "$RUN_BYTES" -d -a 6 --additional-suffix=.run "$TAGGED" "$WORK/r."
fi
rm -f "$TAGGED"
# Primary key + explicit, unique stability tie-break (position field 1).
KEYARGS=(-t "$TAB")
if [ -n "${SORT_KEY:-}" ]; then
# Intentional word-splitting: SORT_KEY may contain several sort arguments.
# shellcheck disable=SC2206
KEYARGS+=($SORT_KEY)
else
KEYARGS+=(-k2)
fi
KEYARGS+=(-k1,1n)
shopt -s nullglob
RUNS=("$WORK"/r.*.run)
shopt -u nullglob
if [ ${#RUNS[@]} -eq 0 ]; then # empty input -> empty output
if [ "$OUT" = "-" ]; then :; else : > "$OUT"; fi
exit 0
fi
# Phase 2: sort each run in place. Key = field 2..end (the record itself);
# tie-break = field 1 numeric (original position).
for f in "${RUNS[@]}"; do
LC_ALL=C sort -s "${KEYARGS[@]}" -o "$f.s" -- "$f"
rm -f "$f"
done
# Phase 3: k-way heap merge with bounded fan-in. Each `sort -m` performs an
# internal k-way heap merge; --batch-size caps k, and we run multiple passes
# until one run remains.
shopt -s nullglob
CUR=("$WORK"/r.*.s)
shopt -u nullglob
pass=0
while [ ${#CUR[@]} -gt 1 ]; do
NXT=()
i=0
while [ $i -lt ${#CUR[@]} ]; do
GRP=("${CUR[@]:i:FANIN}")
i=$((i+FANIN))
if [ ${#GRP[@]} -eq 1 ]; then
NXT+=("${GRP[0]}")
else
out="$WORK/m.${pass}.${#NXT[@]}"
LC_ALL=C sort -m -s "${KEYARGS[@]}" --batch-size "$FANIN" \
-o "$out" -- "${GRP[@]}"
rm -f "${GRP[@]}"
NXT+=("$out")
fi
done
CUR=("${NXT[@]}")
pass=$((pass + 1))
done
MERGED=${CUR[0]}
# Phase 4: strip the position tag and (optionally) collapse duplicates.
# Equal records are now adjacent in original-position order, so `uniq` is a
# stable collapse: it keeps the first occurrence (= earliest in the input).
STRIPPED="$WORK/stripped"
cut -d "$TAB" -f2- -- "$MERGED" > "$STRIPPED"
if [ "$DEDUP" = 1 ]; then
FINAL="$WORK/final"
uniq -- "$STRIPPED" > "$FINAL"
else
FINAL="$STRIPPED"
fi
if [ "$OUT" = "-" ]; then
cat -- "$FINAL"
else
cp -- "$FINAL" "$OUT"
fi
| Requirement | Mechanism |
|---|---|
| Larger than RAM | Phase 1 bounds each run by RUN_BYTES/RUN_LINES; only one run is resident. |
| Hard memory ceiling | sort -m streams; fan-in bounded by FANIN; no full-file buffering. |
| k-way heap merge | sort -m is a k-way heap merge; --batch-size caps k; multiple passes reduce to one file. |
| Duplicate collapse | Phase 4 uniq on sorted output, stable (first wins). |
| Stability | Position tag in field 1 is a unique secondary key (-k1,1n). |
Deterministic LC_ALL=C |
export-style LC_ALL=C on every sort. |
| CRLF / NUL safe | No record byte touches a shell variable; cat -n, split, sort, cut, uniq are byte-transparent. |
| Run size / fan-in tunables | RUN_BYTES/RUN_LINES and FANIN. |
-S counts items, not bytes, and --batch-size must be >= 2; this script deliberately bounds work by splitting runs itself rather than relying on -S.\r is an ordinary data byte (sorts before most bytes under LC_ALL=C), and NUL is an ordinary data byte.sort).All commands below were run in the environment and their observed results are shown.
1. Basic sort + duplicate collapse
$ printf 'banana\napple\ncherry\napple\n' | ./extsort.sh
apple
banana
cherry
$ printf 'b\na\na\n' | DEDUP=0 ./extsort.sh
a
a
b
2. Differential fuzz: random records containing NUL, CR, tabs, and duplicates, multi-pass merge (RUN_LINES=137, FANIN=3)
$ python3 mktest.py 20000 # 20020 records, includes a\x00b, \r, a\tb
$ LC_ALL=C sort -s fuzz.bin | uniq > ref.out
$ RUN_LINES=137 FANIN=3 ./extsort.sh fuzz.bin our.out
$ cmp ref.out our.out && echo MATCH
MATCH
3. Byte-level CRLF and NUL adjacency
$ printf 'b\0\r\nA\r\na\r\nb\0\r\n' > edge.bin
$ ./extsort.sh edge.bin edge.our
$ LC_ALL=C sort -s edge.bin | uniq > edge.ref
$ cmp edge.our edge.ref && echo MATCH
MATCH
$ xxd edge.our
00000000: 410d 0a61 0d0a 6200 0d0a A..a..b...
4. Stability among equal keys with an explicit primary key
Input b1,b2,a3,a4,b2 (tab-separated key<TAB>id), sort key = field 2 (body field 1), DEDUP=0; equal keys must stay in input order:
$ SORT_KEY='-k2,2' DEDUP=0 ./extsort.sh key.in
a 3
a 4
b 1
b 2
b 2 # the position-2 record precedes the position-5 duplicate
$ LC_ALL=C sort -s -t $'\t' -k1,1 key.in
a 3
a 4
b 1
b 2
b 2 # identical => stable
5. Hard memory ceiling and input-size independence
10 MB / 1 M records, run under an 80 MB virtual-memory cap, tiny runs, high fan-in:
$ ( ulimit -v 80000; RUN_BYTES=32768 FANIN=8 ./extsort.sh big.bin big.our3 )
$ cmp -s big.ref big.our3 && echo MATCH-80MB
MATCH-80MB
Peak resident memory with identical tunables, input scaled 5×:
$ /usr/bin/time -v env RUN_BYTES=65536 FANIN=4 ./extsort.sh big.bin /dev/null 2>&1 | grep Maximum
Maximum resident set size (kbytes): 9320 # 10 MB input
$ /usr/bin/time -v env RUN_BYTES=65536 FANIN=4 ./extsort.sh huge.bin /dev/null 2>&1 | grep Maximum
Maximum resident set size (kbytes): 9416 # 50 MB input
Memory stays flat (~9.4 MB) while the input grows 5×, confirming the bound depends on RUN_BYTES/FANIN, not input size.
6. Multi-pass merge at minimum fan-in
$ RUN_LINES=5000 FANIN=2 ./extsort.sh big.bin big.our4
$ cmp -s big.ref big.our4 && echo MATCH-fanin2
MATCH-fanin2
7. I/O modes and syntax
$ printf 'c\nb\na\nb\n' | ./extsort.sh # stdin -> stdout
a
b
c
$ printf 'c\nb\na\nb\n' | ./extsort.sh - out.txt && cat out.txt
a
b
c
$ bash -n extsort.sh && echo "syntax OK"
syntax OK
For whole-record sorts, the oracle is LC_ALL=C sort -s | uniq; for keyed sorts it is LC_ALL=C sort -s -t $'\t' -k<key> | uniq. Every differential test above matched the oracle byte-for-byte.
# Evidence - Problem class: bash-external-merge-sort-bounded-memory-stable - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-03T10:50:50.852Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Write a POSIX bash plus coreutils external sort that orders an input larger than RAM under a hard memory ceiling, using sorted runs and a k-way heap merge followed by a final duplicate-collapse pass. It must be stable, deterministic under LC_ALL=C byte ordering with an explicit tie-break, safe against CRLF and embedded NUL-adjacent records, and expose run-size and merge fan-in as tunables.", "environment": "bash", "language": "shell", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "bash-external-merge-sort-bounded-memory-stable", "provider": "openrouter", "solved_at": "2026-10-03T10:50:50.854Z", "version": "5.2"}