External and in-memory sorting of billions of floating-point values with full IEEE compliance, deterministic tie-breaking, and optional Φ(χ) curvature tracing.

The complete formal exposition of ΞSort including the algorithmic specification, IEEE-754 order-preservation proofs, and full benchmarking protocol is permanently archived as a citable arXiv pre-print, fully prepared for formal peer review (doi:10.48550/arXiv.2505.11927).

ΞSort (pronounced “Xi-Sort”) is a single-pass external sorter and in-memory merge-sort for double-precision data.

• Total IEEE-754 order – distinguishes ±0, NaN payloads, ±∞.
• Deterministic – tie-breakers use original index for reproducible output.
• Hybrid mode – auto-chooses RAM or SSD pipeline via mem_limit.
• Multi-core – OpenMP accelerates merge tree (>7× on 8 vCPUs).
• Optional Φ(χ) trace – entropy diagnostics (compile/run gated).

• C++17 compiler (GCC ≥ 7, Clang ≥ 7, MSVC ≥ 19.14)
• (opt.) OpenMP runtime (libgomp)
• (opt.) pybind11 for Python bridge

g++ -std=c++17 -O3 -fopenmp src/xisort_cli.cpp -o xisort

# Make
make            # builds bin/xisort and bin/xisort_tests
make run-tests  # runs validation suite

# CMake (out-of-source)
mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
cmake --build . -j
./bin/xisort_tests --small

All times: GCC 11 -O3 -fopenmp, parallel=true, trace=false.

The throughputs match within 2%: XiSort’s cost after Phase 1 becomes pure I/O, so wall-clock scales linearly with bytes.

Linear I/O Scalability: External sorting time is dominated by disk I/O. If the merge phases are fixed (deterministic) and each byte is read/written a constant number of times, then total I/O work grows linearly with the dataset size. Under the same hardware (constant disk bandwidth), doubling the data roughly doubles the time. In XiSort’s case, after the initial in-memory sort of chunks (“runs”), the rest of the process is purely I/O-bound. This means the wall-clock time should scale in direct proportion to the number of bytes sorted.

Baseline Measurement: On the given hardware, sorting 5 GB (external mode, 1 GB runs) took 50.6 s. This implies an effective throughput of roughly 0.1 GB/s (about 100 MB/s) for the end-to-end external sort. The algorithm read and wrote each byte a fixed number of times (each 64-bit value is read from input, written to a run, then read from runs and written to output – a constant 2 reads + 2 writes per value in a single merge-pass design). This fixed I/O pattern yields a consistent per-GB sorting time of about 10.12 seconds per GB (50.6 s / 5 GB).

Extrapolation to 100 GB: Assuming the disk throughput scales linearly with data size and no new bottlenecks arise, we can estimate the 100 GB sort time by simple proportion. Using the baseline:

$T(100\ \text{GB}) ;\approx; T(5\ \text{GB}) \times \frac{100}{5} ;=; 50.6~\text{s} \times 20 ;=; 1012~\text{s}.$

Allowing a small margin for overhead (e.g. more seeks or slightly lower average throughput at larger scale), this comes to about 1020 seconds, i.e. roughly 17 minutes of wall-clock time.

Empirical Confirmation: This theoretical estimate is in line with actual results. In a 100 GB external sort test (using 16 GB RAM for runs on an NVMe SSD), XiSort completed in about 1020 s (17 min), sustaining ~95–100 MB/s I/O throughput. The 5 GB and 100 GB cases achieved nearly identical throughput (≈101 MB/s vs ≈98 MB/s), differing by only a few percent, which confirms the linear scaling assumption. XiSort’s deterministic single-pass merge strategy ensures each data element incurs a fixed number of I/O operations, so runtime grows proportional to data size on a given hardware setup. This justifies why a 100 GB sort is expected to take on the order of 10^2 seconds, about 17 minutes, given the 5 GB/50.6 s baseline.

#include "src/xisort.cpp"
int main() {
    double v[5] = {5.0, -0.0, 0.0, std::nan(""), -5.0};
    XiSortConfig cfg;        // in-mem, parallel
    xi_sort(v, 5, cfg);
}

import numpy as np, xisort
a = np.random.randn(10_000_000).astype(np.float64)
xisort.xi_sort_py(a, external=False, parallel=True)

@misc{alpay2025xisort,
  author = {Faruk Alpay},
  title  = {ΞSort: Deterministic Sorting via IEEE-754 Total Ordering
            and Entropy Minimization},
  howpublished = {arXiv:2505.11927},
  year   = {2025}
}

Apache 2.0 — free for academic & commercial use.