Is this parallel sort merge implemented correctly?

Question

Is this parallel merge sort implemented correctly? It looks correct, I took the 40seconds to write a test and it hasnt failed.

The gist of it is i need to sort by splitting the array in half every time. Then i tried to make sure i go wrong and asked a question for a sanity check (my own sanity). I wanted an in place sort but decided that it was way to complicated when seeing the answer, so i implemented the below.

Granted there's no point creating a task/thread to sort a 4 byte array but its to learn threading. Is there anything wrong or anything i can change to make this better. To me it looks perfect but i'd like some general feedback.

static void Main(string[] args)
{
    var start = DateTime.Now;
    //for (int z = 0; z < 1000000; z++)
    int z = 0;
    while(true)
    {
        var curr = DateTime.Now;
        if (curr - start > TimeSpan.FromMinutes(1))
            break;
        var arr = new byte[] { 5, 3, 1, 7, 8, 5, 3, 2, 6, 7, 9, 3, 2, 4, 2, 1 };
        Sort(arr, 0, arr.Length, new byte[arr.Length]);
        //Console.Write(BitConverter.ToString(arr));
        for (int i = 1; i < arr.Length; ++i)
        {
            if (arr[i] > arr[i])
            {
                System.Diagnostics.Debug.Assert(false);
                throw new Exception("Sort was incorrect " + BitConverter.ToString(arr));
            }
        }
        ++z;
    }
    Console.WriteLine("Tried {0} times with success", z);
}
static void Sort(byte[] arr, int leftPos, int rightPos, byte[] tempArr)
{
    var len = rightPos - leftPos;
    if (len < 2)
        return;
    if (len == 2)
    {
        if (arr[leftPos] > arr[leftPos + 1])
        {
            var t = arr[leftPos];
            arr[leftPos] = arr[leftPos + 1];
            arr[leftPos + 1] = t;
        }
        return;
    }
    var rStart = leftPos+len/2;
    var t1 = new Thread(delegate() { Sort(arr, leftPos, rStart, tempArr); });
    var t2 = new Thread(delegate() { Sort(arr, rStart, rightPos, tempArr); });
    t1.Start();
    t2.Start();
    t1.Join();
    t2.Join();
    var l = leftPos;
    var r = rStart;
    var z = leftPos;
    while (l<rStart && r<rightPos)
    {
        if (arr[l] < arr[r])
        {
            tempArr[z] = arr[l];
            l++;
        }
        else
        {
            tempArr[z] = arr[r];
            r++;
        }
        z++;
    }
    if (l < rStart)
        Array.Copy(arr, l, tempArr, z, rStart - l);
    else
        Array.Copy(arr, r, tempArr, z, rightPos - r);
    Array.Copy(tempArr, leftPos, arr, leftPos, rightPos - leftPos);
}

Answer 1

You could use the Task Parallel Library to give you a better abstraction over threads and cleaner code. The example below uses this.

The main difference from your code, other than using the TPL, is that it has a cutoff threshold below which a sequential implementation is used regardless of the number of threads that have started. This prevents creation of threads that are doing a very small amount of work. There is also a depth cutoff below which new threads are not created. This prevents more threads being created than the hardware can handle based on the number of available logical cores (Environment.ProcessCount).

I would recommend implementing both these approaches in your code to prevent thread explosion for large arrays and innefficient creation of threads which do very small amounts of work, even for small array sizes. It will also give you better performance.

public static class Sort
{
    public static int Threshold = 150; 

    public static void InsertionSort(int[] array, int from, int to)
    {
        // ...
    }

    static void Swap(int[] array, int i, int j)
    {
        // ...
    }

    static int Partition(int[] array, int from, int to, int pivot)
    {
        // ...
    }

    public static void ParallelQuickSort(int[] array)
    {
       ParallelQuickSort(array, 0, array.Length, 
            (int) Math.Log(Environment.ProcessorCount, 2) + 4);
    }

    static void ParallelQuickSort(int[] array, int from, int to, int depthRemaining)
    {
        if (to - from <= Threshold)
        {
            InsertionSort(array, from, to);
        }
        else
        {
            int pivot = from + (to - from) / 2; // could be anything, use middle
            pivot = Partition(array, from, to, pivot);
            if (depthRemaining > 0)
            {
                Parallel.Invoke(
                    () => ParallelQuickSort(array, from, pivot, depthRemaining - 1),
                    () => ParallelQuickSort(array, pivot + 1, to, depthRemaining - 1));
            }
            else
            {
                ParallelQuickSort(array, from, pivot, 0);
                ParallelQuickSort(array, pivot + 1, to, 0);
            }
        }
    }
}

The full source is available on http://parallelpatterns.codeplex.com/

You can read a discussion of the implementation on http://msdn.microsoft.com/en-us/library/ff963551.aspx