Runtime: Provide a sorting algorithm with good behavior on nearly-sorted inputs.

[CyrusNajmabadi]

The existing 4.5 Array.sort is implemented with intro sort. While this has reasonable behavior, it effectively has the same number of comparisons regardless of input size. This number of comparisons is (as expected) around n * log_n. While this is acceptable for random inputs, it is unfortunately much slower for nearly-sorted inputs. More recent algorithms (like TimSort) can provide massive improvements here, sorting nearly-sorted lists with a nearly linear number of comparisons.

For code-paths where sorting is expensive, and where comparisons are not cheap, a better sort algorithm built into the Fx would be appreciated.

Whether or not this becomes the default is up to you. But providing it as an option would still be a huge boon.

Note: this hits Roslyn+TypeScript. We often produce trees (i.e. for tagging) from nearly sorted data. There may be hundreds of thousands of elements in this data. Being able to sort in near-linear time means we can then build our trees in linear time. With data sets this large, the difference between n and n log n is actually quite significant.

[karelz]

Changing sorting algorithm might be dangerous from compat perspective.
I have hard time to imagine a new API name (Sort_GreatBehaviorIfAlmostSorted?)
I also wonder if it wouldn't be better to create a library which sits on top of .NET Core. Maybe this is not the best thing to have directly embedded in the platform.

Thoughts?
cc: @weshaggard @terrajobst @Priya91

[CyrusNajmabadi]

Maybe this is not the best thing to have directly embedded in the platform.

Out of curiosity, why? Other platforms (like Java) provide this and that's a good thing IMO.

[karelz]

Out of curiosity, why?

Feels to me like rather specific API, not a problem majority of devs will hit. Anyway just my view point (may be wrong).

Other platforms (like Java) provide this and that's a good thing IMO.

I wasn't aware of that. Would you have suggestion based on the other platforms then? Formal API proposal is the next thing needed.

[CyrusNajmabadi]

Feels to me like rather specific API

Note: i'd prefer it to _not_ be a specific API. I'd far prefer the default Sort to just actually be good at dealing with inputs of a certain form. That's one of the reasons it's the default for Python and why Java uses it as well. It's not only very good at the worst inputs, but it's _extremely great_ at certain types of inputs that do arise in practice.

[karelz]

By specific I meant, not commonly needed.

If there are no compat concerns from others (@weshaggard @terrajobst), I'll be fine with that as well.
Obviously such change should come with perf tests and perf measurements comparing the old vs. new behavior (on nearly-sorted and random inputs).

@weshaggard @terrajobst would you be fine with changing Array.Sort algorithm from compat point of view?

[weshaggard]

From a compat prospective it is definitely high risk. When we switched to IntroSort in the framework we broke all sorts of things from different errors conditions to different stable sorting behavior. We spent a lot of time digging out of the whole on that switch and had to add a bunch of quirks. From that experience I would be very hesitant to change the core sorting algorithm but instead would recommend a library on top of the core that implements specific sorting algorithms that people are interested in.

[karelz]

That's what I was afraid of. Seems like creating standalone library with assortment of sorting algorithms is the best approach here.

[CyrusNajmabadi]

That's what I was afraid of. Seems like creating standalone library with assortment of sorting algorithms is the best approach here.

I feel like closing this out is premature. I don't doubt risk. But i assume that's why we have tests. And presumably through the last round of doing this, we invested in appropriate testing to ensure these behaviors were preserved. Furthermore, even if we don't change the core sorting algorithm, this could still go in 'CoreFx'. Good data structures and algorithms benefit everyone. We should be trying to provide these things to fill the needs of all the layers we build on top of us.

And, as mentioned before, this is already something that other very popular platforms already provide. Users of those platforms can trust that they have a great base of functionality to build on top of for core CS needs.

[AlexGhiondea]

I think CoreFx would be a good place for that kind of library. We can prototype it in CoreFxLabs and then move it over once it is ready.

But I don't think we can/should change the default sorting behavior.

[karelz]

OK, 2 votes for special library, 2 votes for in CoreFX (via CoreFxLabs). Reopening for now.
We need formal API proposal review first - it's up for grabs.
If the API shape is approved, we can give a green light to anyone interested in implementing it.

[pgolebiowski]

@CyrusNajmabadi @karelz @AlexGhiondea

Code is expressible, self-documented, extendable:

interface ISortingAlgorithm
{
    void Sort<T>(IList<T> collection)
}

interface IStableSortingAlgorithm : ISortingAlgorithm
{

}

class TimSort : IStableSortingAlgorithm
{
    public TimSort();

    public void Sort<T>(IList<T> collection);
}

Any thoughts?

Plus in the future no concerns like the ones @weshaggard mentioned. Also solves this issue.

[karelz]

Where in CoreFX would you use each interface? (esp. the Stable interface)

[pgolebiowski]

I rather thought that users of CoreFX could benefit from this, not the standard library itself (although there might be some appropriate usage -- haven't meditated over that). My though process was that:

• These interfaces provide layers of abstraction that facilitate conceptual explanation of the code. I like .NET very much for its carefully designed API. Writing well-crafted and self-explanatory software is almost as important as writing working software. Here, I intended to use interfaces to further describe the intent of the software. With the support of an IDE, one could easily see that a class (here TimSort) implements IStableSortingAlgorithm. Thus, no need to go browse the Internet for whether it is stable or not.
• Moreover, with such an approach, the API will remain intact even 20 years if new sorting algorithms will be desired to have. Then still, implementation-agnostic classes that just use ISortingAlgorithm or IStableSortingAlgorithm will still be valid and may benefit from those new approaches while not changing them. If instead we use some static methods — we are asking for trouble, as it is very poorly extendable later.
• A user might be willing to reuse some of CoreFX interfaces, providing their own implementations. These implementations would then still fit whatever class depending on sorting algorithms they come across.
• Easier testing.

I am OK if you don't like the approach :) I understand the concerns and they're also valid. Would be very happy to know how to do this in a clear way while not producing too much overhead.

[karelz]

The key question is: How often people need to choose specific sorting algorithm? 99.9% usages just don't care (assuming it is not horrible algorithm). We need to optimize for those usages - especially around usability, while not stopping the 0.1% case from being possible.

IMO the 0.1% case can search documentation. If something in VS pops it for them (VS itself / opt-in extension), then great! Of course assuming it doesn't hurt the user experience of 99.9% case - you don't want pop ups for those cases.

[pgolebiowski]

This is true, but if:

• We don't want to change the current implementation of the sorting algorithm (Array.Sort())
• We don't want to add a possibility of custom sorting algorithms as classes
• An extension method stating something like Sort_GreatBehaviorIfAlmostSorted hurts the user experience in 99.9% cases, as it pops something they don't care about

Then I'm not sure if we should consider adding this functionality at all... PowerCollections?

[karelz]

We don't want to change the current implementation of the sorting algorithm (Array.Sort())

most likely correct, due to AppCompat - these low-level things tend to break people. So any change has to bring the benefits over the bad impact.

We don't want to add a possibility of custom sorting algorithms as classes

What do you mean exactly? Giving it as input to Array.Sort(ISortingAlgorithm)?
You can implement your sorting algo classes today, you just cannot inject them into existing APIs today -- the question is: Which APIs? And could it be done differently? (e.g. via extension methods, or via different pattern) Do I really need yet-another-overload on core types?

An extension method stating something like Sort_GreatBehaviorIfAlmostSorted hurts the user experience in 99.9% cases, as it pops something they don't care about

First, we do not add weird names like "OnlyForExperts". We usually add overloads, or easy-to-comprehend methods. People will look at them and they should be self-describing in ideal case. And they should be believed to be useful for many ...
With the pop I reacted to your idea of VS tooling pops.

Overall, personally I agree that bundling it with PowerCollections is better option. I can be over-voted though.

[pgolebiowski]

What do you mean exactly? Giving it as input to Array.Sort(ISortingAlgorithm)?

Yes, for example. I meant adding those interfaces and classes I suggested before (ISortingAlgorithm + stuff like TimSort : ISortingAlgorithm). I think it was the only option not to be overly messy with the API...

We usually add overloads, or easy-to-comprehend methods. People will look at them and they should be self-describing in ideal case. And they should be believed to be useful for many ...

That is why I don't believe in adding "a sorting algorithm with good behavior on nearly-sorted inputs". If the functionality isn't really needed plus there is no way to add it in a graceful way, I think we should close the issue.

[karelz]

Yes, for example. I meant adding those interfaces and classes I suggested before

It would be helpful for further discussion to suggest more complete list of such APIs.

If there is no way to add this functionality in a graceful way, I think we should close the issue.

I agree :). Let's see if someone else has ideas we didn't see. Or disagrees strongly with some of the statements/requirements I mentioned above ...

[pgolebiowski]

@karelz

I agree :). Let's see if someone else has ideas we didn't see. Or disagrees strongly with some of the statements/requirements I mentioned above ...

• I'm not pushing anything, but it's been a while since then. :smile:
• How does the process of closing issues look like? Is there anything formalized for scenarios where the proposal is rejected by Microsoft and community + there is no one willing to disagree anymore?
• I know someone might still come and disagree, it's been just only 7 weeks. Just wondering when we can take some action.

[karelz]

We do not have any process on closing issues. It is brewing in the back of my mind for last few weeks. I plan to review all API suggestions and close those we do not plan to take, more aggressively (yet in a polite way) -- I think it is healthy communication to the community which APIs we might consider and which we are convinced are not good fit for CoreFX repo. It may spark interesting discussions. It is at minimum transparent way to communicate our intent.

Such reviews are somewhat blocked on ideally having another CoreFXExtensions repo with PowerCollections and friends, to make it easier for community to party on advanced APIs in a common repo (not dealing with nuget publishing, test infra, etc.).
Sadly, there are disagreements on our team about that concept (alternative: let community stand up such repo itself and drive it & govern itself). I am still working through those discussion. It will take some time and I won't make any progress over summer for sure. (just to set time expectations)
To speed up things I may create issue "Great candidates for external repo" and close the bad fits in CoreFX against that one. Gotta think it through. I'll try to get to it in July.

[karelz]

Included in dotnet/corefx#20902, closing.