I'm building an interpreter and need to create a function in my standard library that sorts based on a user-defined comparator. This comparator must be async, so this requires a sorting function itself is async (using Tasks).
Is there an existing .NET sorting function that allows Tasks in the comparer? That is, the comparer returns a Task<int> and the sorting function completes the Task and uses the int to sort.
For example, a version of the List.Sort(IComparer<T>) function where Compare(T,T) returned a Task<int> instead of an int.
(I'm using F# but happy to use C# libraries)
Edit: imagine the comparer needed to make a HTTP POST to compare two items.
You could implement an async mergesort implementation that would do that.
And in fact, the Wikipedia article on Mergesort actually discusses parallel implementations.
The basic algorithm is simplicity itself:
If your list is a linked list, no extra memory is needed, as the next point provides all that's needed.
If your list is an array-like construct, then you have to eat extra memory to create working arrays for each half as an in-place merge is not very practical.
Edited to note: Here's a little paperlet from Microsoft on implementing a .Net parallel mergesort with multiple partitions, not just 2: https://devblogs.microsoft.com/pfxteam/parallel-merge-sort-using-barrier/