Any interest in collaborating?

[EamonNerbonne]

I found this repo via dotnet/corefx#26859 and https://github.com/dotnet/corefx/issues/15329 and you mentioned that you wanted to publish a package.

I independently did just that in https://github.com/EamonNerbonne/anoprsst; but the focus isn't quite the same, and I wouldn't mind merging the efforts to avoid some duplication of effort and improve the quality.

In particular, since I didn't need it, I didn't implement introsort/heapsort, and did not try to keep "bogus-comparer" compatibility with the current Array.Sort. I can imagine the API isn't to everyone's taste either.

However, I did add a parallel version and spent some time on micro-optimization which may or may not have payed off (I didn't compare it with this version, but Array.Sort appears fairly easy to beat).

[EamonNerbonne]

I get that you're perhaps a little disappointed with how things went on dotnet/corefx#26859 - and similarly this is not at all a priority for me; but if you're mildly interested I might start copy-pasting code from this repo (particularly the introsort bits) and discuss api issues.

[dzmitry-lahoda]

It seems very interesting and very long term effort to do sorting right. Sort large structures? Ref comparison? Sort with no thread usage overhead? For actors, cooperative servers and game loops. Zero GC sorting? Sorting of classes vs unmanaged structs? Improve sort using BitOperations from 3.0? May be. Best possible sort API - balance of compatibility and breaking bad thing for good and consistency and clearance(choose right sorted for you data and environment). Documentation, testing, harness, releases. Unite sorting efforts? Continue changes and push efforts into corefx.

@EamonNerbonne , are you going to work on such kind of project long term?

[EamonNerbonne]

I think it's a fun project, but I'm a little leery of a project that can't go anywhere; and the discussions in dotnet/corefx#26859 failed rather late in the process which isn't encouraging, and part of the problem was usage of unsafe code, which I suspect is going to have quite a significant impact.

[EamonNerbonne]

So I wouldn't mind a fun project with a pragmatically fast api, but my hopes of getting such a thing into corefx are low.

Zero GC sorting with low overhead is simply a matter of quicksort, I guess, which is in this repo and anoprsst, but then you don't get multithreading - if you want multithreading, you need a few allocations (very few, but still).

[dzmitry-lahoda]

Usage of unsafe of Unsafe?

Unsafe was invented 10 years ago, and now part of corefx. Span, ranges, etc - also several years ago (as I recall many innovation where from StackExchange and ASP.NET DNX).
So it takes time.

Some things are not adopted as whole, but best integration parts are integrated into.
If this project or anoprsst will get 500 starts, so at that time some parts of API(or some algorithms) will migrate into corefx as people need such stuff. Like IObserver in corefx, but with no implementation. Or there is no unit, but I can create unit for all via Roslyn Analyzer.

I imagine sorting project as long therm research and development (because of variability described above, and additional one from hardware I have not mentioned). After some time proper separation of code (sharded for sorters and custom) will appear.

My interest steams from full struct only design of things:

                    //TODO: use ref compare-sort https://github.com/dotnet/corefx/issues/33927
                    node.ComplexNode.children = node.ComplexNode.children.OrderBy(x => x.totalOffset).ThenByDescending(x => x.size).ToArray();
node.totalOffset = node.ComplexNode.children[0].totalOffset;

But I imagine that I just will copy some code from you and use.

[EamonNerbonne]

This isn't actually my repo, perhaps we should move this discussion elsewhere...

[nietras]

Closed as I am not interested in parallelization here and since this issue is old, sorry about that guys :) I am tentatively planning on finalizing this code and releasing a nuget package for it. Sometime. Lately, dotnet core has seen some updates to the code in that which makes it better and implements the Span as I proposed, although not optimally. I hope to do that here, and to then have a package that can be used on old runtimes e.g. .NET Framework, not just .NET 5.0.