zSort: Breaking the "Stability Tax" with Z-Score Partitioning

Forum topic · 小凯 · 2026-05-16

Summary

Stable sorting preserves the original order of equal elements but typically runs slower than unstable sorts, forcing databases and data pipelines to trade correctness guarantees for speed. zSort, described in the preprint "zSort: Stable Distribution Sort using Z-Score Partitioning" (arXiv:2605.14419, cs.DS) by Hriday Jain, Ketan Sabale, Aditya Shastri and colleagues, tackles this "stability tax" using z-score partitioning. Instead of fixed radix boundaries, zSort computes z-scores (value minus mean, divided by standard deviation) and uses their distribution to dynamically determine partition boundaries, enabling distribution-based sorting with stability guarantees. Microarchitecturally, the algorithm shows low branch misprediction overhead (19.7%) and an IPC of 1.44. In practice, it is reported to be 3-4.5x faster than stable sorts and approaches LSD Radix performance, with even bigger gains on inputs containing many duplicate values. The forum post notes caveats: the paper offers no tight theoretical bound proof, framing the work primarily as engineering innovation, and z-score partitioning stability is only evaluated on common data distributions.

Stable sorting preserves the original relative order of equal elements, but stable sorts are typically slower than unstable ones. This "stability tax" forces databases and data pipelines to make trade-offs. zSort uses z-score partitioning to perform distribution-based sorting while guaranteeing both stability and high performance.

How it works

The z-score is defined as:

> z-score = (value - mean) / standard deviation

Rather than relying on fixed radix digits, zSort uses the distribution of z-scores across the data to dynamically determine partition boundaries.

Performance

Microarchitecture: branch misprediction overhead is only 19.7%, with an IPC of 1.44
End-to-end: 3-4.5x faster than stable sorts, approaching LSD Radix performance
Duplicates: the advantage grows even larger on inputs with many repeated values
Stability: achieved without sacrificing speed

Caveats (from the original poster)

> zSort has no proof of a tight theoretical bound — it is more of an engineering innovation. Is z-score partitioning stable across all distributions? The paper only benchmarks common distributions.

Paper information

Title: zSort: Stable Distribution Sort using Z-Score Partitioning
Authors: Hriday Jain, Ketan Sabale, Aditya Shastri, et al.
Preprint: arXiv:2605.14419 (cs.DS)
Link: https://arxiv.org/abs/2605.14419