.NET 中的异步排序（使用任务）

Question

我正在构建一个解释器，需要在我的标准库中创建一个基于用户定义的比较器进行排序的函数。这个比较器必须是异步的，所以这需要一个排序函数本身是异步的（使用Tasks）。

是否存在允许比较器中的任务的现有 .NET 排序功能？也就是说，比较器返回 a Task<int>，排序函数完成Task并使用int进行排序。

例如，List.Sort(IComparer<T>)函数的一个版本Compare(T,T)返回 aTask<int>而不是int。

（我正在使用 F# 但很高兴使用 C# 库）

编辑：想象一下比较器需要制作一个 HTTP POST 来比较两个项目。

Answer 1

您可以实现一个异步合并排序实现来做到这一点。

事实上，维基百科关于Mergesort 的文章实际上讨论了并行实现。

基本算法本身很简单：

• 从要排序的项目列表开始
• 如果它的长度是 0 或 1，你就大功告成了：它们已经按定义排序了。
• 将该列表分成两半
• 递归合并排序每一半，然后
• 将它们合并在一起。

如果您的列表是链表，则不需要额外的内存，因为该next点提供了所需的一切。

如果您的列表是一个类似数组的构造，那么您必须消耗额外的内存来为每一半创建工作数组，因为就地合并不是很实用。

编辑注意：这是微软关于实现具有多个分区的 .Net 并行合并排序的小文件，而不仅仅是 2 个：https ://devblogs.microsoft.com/pfxteam/parallel-merge-sort-using-barrier/