Adaptive Parallel Multimerge Sort in Rust

Hi Arrow maintainers,

I am sharing a research-driven sorting engine implementation written in Rust, which focuses on minimizing the synchronization cost of parallel sorting in buffer-heavy workloads—a core challenge within the Arrow ecosystem.

The engine implements two key innovations:

Adaptive Oscillation Heuristic: An entropy-based sampling strategy that dynamically switches between sequential insertion sort and parallel work-stealing merge paths based on real-time data distribution analysis.

Bidirectional (Convergent) Merging: A strategy that processes data from buffer edges towards the center. This approach significantly improves cache-line utilization and reduces total memory traffic compared to unidirectional merge patterns.

By utilizing a zero-copy approach, this engine achieves up to 38x speedups on high-entropy (random) datasets compared to standard managed-runtime implementations.

I am presenting this as a proposal for the Arrow compute module's sorting path. I am eager to get feedback from the maintainers regarding how such entropy-aware heuristics could potentially align with the current arrow-rs sorting implementation, particularly concerning compatibility with existing Array layouts.

Project details & Benchmarks: [[Adaptive Parallel Multimerge Sort in Rust](https://github.com/fbcouto/adaptive-parallel-multimerge-sort)]
Technical Deep Dive: (https://medium.com/p/f2b3e4743e3e?postPublishedType=initial)

I look forward to your insights on the feasibility of integrating these adaptive sorting paradigms.

Start by reading the current arrow-rs sorting implementation in the Arrow compute module and reviewing the linked adaptive-parallel-multimerge-sort project and benchmarks. Check how the proposed heuristics and zero-copy approach would interact with existing Array layouts. The issue does not define an implementation scope or acceptance criteria; done would require maintainers to agree on a concrete integration plan.

Written by the indexing model from the issue text.