Updating sort algorithms

[nazar-pc]

Rust library today uses ipnsort and driftsort for unstable and stable sort respectively.

I'm wondering if it would make sense to switch to them in parallel implementations here too instead of pdqsort and timsort respectively.

[cuviper]

Yes -- our current implementations were originally copied and adapted from the standard library, and we've synced some minor tweaks since then, but not that major rewrite yet. I'd be happy to see the new ones ported!

It might be even better if we can just do the parallel splits and merges on our own, and forward the rest to the standard library. I think that may be feasible for the unstable sort, but last time I looked, the buffer management of stable sorting is not amenable to that kind of arrangement.

[nazar-pc]

I'd actually be interested in something like that being exposed in a public API. I already have a parallel operation that creates a bunch of vectors with intermediate results with the size roughly proportional to the performance of the corresponding CPU core.

What happens next is concatenating them into a new vector prior to running parallel sort. If there was only a way to efficiently sort intermediate results in their threads and them merge together into the final sorted output, that might potentially make the whole thing more efficient.

Sorting is a very non-negligible part of the performance-sensitive code in that case.

[mtantaoui]

I'm interested in contributing to this by integrating two new parallel sorting algorithms (ipnsort and driftsort) into Rayon. I want to follow Rayon’s design conventions for the public API.

I'm considering two possible approaches to expose these algorithms:

• Adding new methods: For example, adding par_ipn_sort and par_drift_sort to the ParallelSliceMut trait (similar to how par_sort and par_sort_unstable are implemented).
• Extending par_sort: By adding an argument (such as an enum or parameter) to choose the algorithm within the existing par_sort method.

Is there a preferred approach according to Rayon's API design philosophy? Should new sorting algorithms typically be exposed as separate methods, or is it more idiomatic to extend the existing method with options? Are there any examples or guidelines in Rayon on how to handle multiple algorithm choices in the API?

I appreciate any guidance on this, as I want to ensure the contribution aligns with Rayon’s conventions. Thank you for your time and feedback!

[nazar-pc]

I would have expected the same as what was done in the standard library: previous implementation is removed, new added, method names or signatures stay the same.

[adamreichold]

To add to the previous comment: If these algorithms are strictly better than the existing code, why not replace the implementations but keep the API the same. And if for some reason, keeping the existing implementations around is necessary, I would argue the separate methods are preferable as they do not break backwards compatibility for existing users.