Parallel Sort Algorithm

Question

I'm looking for a simple implementation of a parallelized (multi-threaded) sort algorithm in C# that can operate on List<T> or Arrays, and possibly using Parallel Extensions but that part isn't strictly necessary.

Edit: Frank Krueger provides a good answer, however I wish to convert that example to one that doesn't use LINQ. Also note that Parallel.Do() seems to have been superceded by Parallel.Invoke().

Thanks.

Answer 1

From "The Darkside" in his article Parallel Extensions to the .Net Framework we have this parallel extensions version of quicksort:

(Edit: Since the link is now dead, interested readers may find an archive of it at 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));
        }
    }
}

Notice that he reverts to a sequential sort once the number of items is less than 2048.