polyphaseSort

polyphaseSort

Polyphase merge sort — the fixed-file-budget companion to sort. It uses exactly K files (default 4) regardless of input size, which suits bounded file budgets and storage spread across drives / buckets / machines (one wrapper each). Like sort, it sorts data far larger than memory.

import polyphaseSort from 'stream-sorting/polyphase-sort.js';

for await (const item of polyphaseSort(input, {
  compare: (a, b) => a - b,
  k: 4,
  tmpDir: '/var/sort'
})) {
  // ascending order
}

Same in/out shape as sort: accepts AsyncIterable<T> | Iterable<T>, returns AsyncIterable<T>.

Options

Pass a comparator (compare or lessFn) and storage (files, or k with tmpDir / createWrapper).

Option	Type	Default	Description
compare	(a, b) => number	—	Comparator, Array.prototype.sort semantics. Provide this or lessFn.
lessFn	(a, b) => boolean	—	Strict-less comparator. Provide this or compare.
files	ObjectStreamWrapper[]	—	Explicit wrappers, one per file (K = files.length, minimum 3). User-owned: closed, not deleted.
k	number	4	Number of files (minimum 3). Use with tmpDir or createWrapper.
tmpDir	string	—	Directory for k built-in LocalFileWrapper files. No default (tmpfs footgun).
createWrapper	(fileIndex) => ObjectStreamWrapper	—	Factory for the k file wrappers.
batchSize	number	10000	Soft cap on in-memory items per run.
stable	boolean	true	Keep input order for equal items.
onProgress	(stats) => void	—	Progress callback (see below).
keepTempFiles	boolean	false	Keep temporary files instead of deleting them.

Spread I/O across backends by passing files — e.g. one wrapper per drive, S3 bucket, or remote machine.

Progress

interface PolyphaseSortProgressStats {
  phase: 'pre-sort' | 'merge' | 'final-merge';
  itemsRead: number;
  itemsWritten: number;
  passesComplete: number;
  virtualSeries: number; // virtual (empty) runs used to pad the distribution
  files: Array<{role: 'input' | 'output' | 'idle'; runsRemaining: number}>;
}

Algorithm

1. Distribute. Pull items into sorted batches (runs) and write them across K − 1 input files, filling a perfect Fibonacci distribution. Where the real run count is not perfect, the shortfall is tracked as virtual (empty) runs.
2. Merge in phases. Repeatedly merge the K − 1 inputs into the one output file; a run ends at a sort-order break (lessFn). When an input file's runs are exhausted it becomes the next output and the old output rejoins the inputs.
3. The last merge (every file down to ≤ 1 run) streams straight to the caller. When the input fits in a single batch it is sorted in memory and emitted directly.

Accidentally adjacent in-order runs simply read back as one longer run; the run counts stay arithmetic and the file end (EOF) corrects the bookkeeping. Stability uses an internal monotonic tag, essential here because items are reshuffled across passes.

See also: sort, ObjectStreamWrapper.