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.