Async Sorting (using Tasks) in .NET

Question

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.

Answer 1

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:

• Start with a list of items to be sorted
• If its length is 0 or 1, you're done: they are already sorted by definition.
• Partition that list into two halves
• Recursively merge sort each half, and then
• merge them together.

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/