Is this parallel merge performed correctly?

Question

Is this parallel merge sort done correctly? It looks right, I took 40 seconds to write a test, and it did not work.

Its essence is that I need to sort by breaking the array in half each time. Then I tried to make sure that I was wrong, and asked a question about checking sanity (my own mind). I wanted to post the sort , but decided that it was difficult to complicate when viewing the answer, so I implemented below.

There is no point in creating a task / thread to sort a 4 byte array, but to study threads. Is there something wrong or something that I can change to make it better. It looks perfect to me, but I would like to get 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 can use a parallel task library to give you better thread abstraction and cleaner code. The following example uses this.

The main difference from your code, in addition to using TPL, is that it has a cutoff threshold below which a sequential implementation is applied regardless of the number of threads running. This prevents the creation of threads that do very little work. There is also a depth limit below which no new threads are created. This prevents the creation of new threads than the hardware can process based on the number of logical cores available (Environment.ProcessCount).

I would recommend implementing both of these approaches in your code to prevent the flow of explosions for large arrays and inefficient creation of threads that do very little 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 at http://parallelpatterns.codeplex.com/

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