v1.0.5

Changed

• Final output is now a verbatim byte copy. The last merged chunk is
  already in the exact output format ([int64 count][item]...), so Sort()
  copies its bytes straight to the output stream instead of deserializing and
  re-serializing every record. This removes a whole pass of per-record
  (string) allocation from the hot path.
  • Measured on the 50K end-to-end benchmark (Ryzen 9800X3D): allocation
    ~23.75 MB → ~21.8 MB (~8% less), and ~9–14% faster end-to-end
    (e.g. P=8 15.41 ms → 13.30 ms). Output is byte-identical
    (Read ∘ Write round-trips the format exactly).

v1.0.4 — parallel merge (~1.54×) + robustness pass

ExternalSorting.Core v1.0.4

Parallel merge — the headline

The multi-pass merge used to be fully single-threaded; only chunk creation
ran in parallel, so Amdahl's law capped the end-to-end speedup at ~1.20×
no matter how many cores were free. Within a pass the batches are independent
(each reads its own group of chunk files and writes one merged output), so
they now merge concurrently.

Measured on a Ryzen 9800X3D (same box, same config — only the merge
implementation differs, so the delta is the code, not the hardware):

Parallelism	Serial merge	Parallel merge	Speedup
1	23.72 ms	23.70 ms	1.00×
2	21.12 ms	17.93 ms	1.32×
4	19.82 ms	15.75 ms	1.50×
8	20.20 ms	15.41 ms	1.54×
16	20.90 ms	15.73 ms	1.51×

End-to-end scaling 1.20× → 1.54×, sweet spot moved P=4 → P=4–8,
~−24% wall-clock at P=8. The serial path (P=1) is unchanged and output is
byte-identical. Peak merge RAM now scales with DegreeOfParallelism.

Robustness pass

• Option validation in the constructor: non-null serializer/comparer,
  MergeWayCount >= 2 (a 1-way merge never converged → was an infinite loop),
  positive memory/buffer, DegreeOfParallelism >= 1, non-empty temp dir,
  positive EstimatedItemSize; Sort() null-guards its streams.
• Leak-safe streams: input readers use leaveOpen: true and are disposed;
  merge readers and replacement-selection writers are released in finally on
  fault; a reader-thread fault in the parallel pipeline cancels and drains the
  workers before propagating (no worker writes into a temp dir being deleted),
  and a worker fault is no longer masked by the reader's induced cancellation.
• Int64 count headers everywhere (chunk files + final output) so sorts
  beyond int.MaxValue items don't corrupt counts.
• Real metrics: SortMetrics.BytesRead / BytesWritten are now populated
  (cheap Position delta for seekable streams, counting-stream fallback
  otherwise — no hot-path cost in the common case).
• Docs: stream-ownership + unstable-sort semantics on IExternalSorter,
  binary record format on RecordSerializer.

Tests

Suite 51 → 71: option/null validation, fault cleanup across all three
chunk strategies, a cross-platform proof that the parallel fault path drains
blocked workers, Int64 header, truncated-input EOF handling, leaveOpen,
metrics, and a deep multi-pass parallel-merge byte-identical check.

Compatibility

The on-disk chunk format and the final output header are now Int64 (8-byte)
counts. If you previously persisted sorter output and parse the count header
yourself, read it as Int64.

v1.0.3

Highlights

Performance optimization series — three independent wins, each measured with BenchmarkDotNet:

• MinHeap.ReplaceMin fast path in the merge inner loop: 30% faster at K=8, 34% at K=16. Replaces ExtractMin + Insert (two heap ops) with Peek + ReplaceMin (one heap op) when the source still has more data.
• Pipelined parallel chunk creation: SortOptions.DegreeOfParallelism is no longer a dead option. One reader thread feeds N sort+write workers via a bounded BlockingCollection. ~1.12× speedup at P=4 on a 4-physical-core box for in-memory workloads (wider for disk-bound).
• Knuth's Replacement Selection algorithm (SortOptions.UseReplacementSelection): produces runs that average 2× the heap size for random input. On a 50K-record dataset with 32 KB heap: 74 chunks → 38 chunks (49% fewer), 3 → 2 merge passes, 32% less memory allocated.

Test count grew from 35 → 51 covering RS correctness, parallel determinism stress, race conditions, cancellation safety. New tests/ExternalSorting.Benchmarks/ project with three BenchmarkDotNet suites (MergeBenchmarks, ChunkStrategyBenchmarks, SortBenchmarks).

Backward compatible: every new feature is opt-in via SortOptions, defaults preserve previous behavior except DegreeOfParallelism which now actually does something (was declared but unused before).

Changes since v1.0.2

• release v1.0.3 — perf benchmarks, README, version bump
• test(parallel): correctness + race + cancellation coverage for parallel chunk creation
• feat(chunk): Replacement Selection algorithm for ~2x larger runs
• test(bench): BenchmarkDotNet project for end-to-end sort
• perf(chunk): pipelined parallel chunk creation honoring DegreeOfParallelism
• perf(merge): use ReplaceMin in MergeBatch hot loop

v1.0.2

ExternalSorting.Core v1.0.2

• Fix PackageProjectUrl → GitHub Pages site

Install

dotnet add package ExternalSorting.Core --version 1.0.2

v1.0.1

ExternalSorting.Core v1.0.1

NuGet package for k-way external merge sort in .NET 8.

Install

dotnet add package ExternalSorting.Core --version 1.0.1

What's included

• Generic IExternalSorter<T> — plug in any record type, comparer, and serializer
• Binary min-heap k-way merge — O(N log K)
• Memory-adaptive chunking, progress reporting, cancellation support