c# - 并行排序算法

Question

我正在寻找可以在 List<T> 上运行的 C# 中并行(多线程)排序算法的简单实现。或数组，并可能使用并行扩展，但这部分并不是绝对必要的。

编辑:Frank Krueger 提供了一个很好的答案，但我希望将该示例转换为不使用 LINQ 的示例。另请注意 Parallel.Do()似乎已被 Parallel.Invoke() 取代.

谢谢。

Answer 1

来自他文章中的“黑暗面”Parallel Extensions to the .Net Framework我们有这个并行扩展版本的快速排序:

(编辑:由于链接现已失效，感兴趣的读者可以在 the Wayback Machine 找到它的存档)

private void QuicksortSequential<T>(T[] arr, int left, int right) 
where T : IComparable<T>
{
    if (right > left)
    {
        int pivot = Partition(arr, left, right);
        QuicksortSequential(arr, left, pivot - 1);
        QuicksortSequential(arr, pivot + 1, right);
    }
}

private void QuicksortParallelOptimised<T>(T[] arr, int left, int right) 
where T : IComparable<T>
{
    const int SEQUENTIAL_THRESHOLD = 2048;
    if (right > left)
    {
        if (right - left < SEQUENTIAL_THRESHOLD)
        {

            QuicksortSequential(arr, left, right);
        }
        else
        {
            int pivot = Partition(arr, left, right);
            Parallel.Do(
                () => QuicksortParallelOptimised(arr, left, pivot - 1),
                () => QuicksortParallelOptimised(arr, pivot + 1, right));
        }
    }
}

请注意，一旦项目数少于 2048，他就会恢复为顺序排序。