Skip to content

Instantly share code, notes, and snippets.

@wieslawsoltes
Created September 17, 2013 10:21
Show Gist options
  • Save wieslawsoltes/6592526 to your computer and use it in GitHub Desktop.
Save wieslawsoltes/6592526 to your computer and use it in GitHub Desktop.
C# Parallel Sort
#region References
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
#endregion
namespace ParallelSort
{
#region Parallel Sort
public static class Sort
{
public static int Threshold = 150; // array length to use InsertionSort instead of SequentialQuickSort
public static void InsertionSort<T>(T[] array, int from, int to) where T : IComparable<T>
{
for (int i = from + 1; i < to; i++)
{
var a = array[i];
int j = i - 1;
//while (j >= from && array[j] > a)
while (j >= from && array[j].CompareTo(a) == -1)
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = a;
}
}
static void Swap<T>(T[] array, int i, int j) where T : IComparable<T>
{
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
static int Partition<T>(T[] array, int from, int to, int pivot) where T : IComparable<T>
{
// Pre: from <= pivot < to (other than that, pivot is arbitrary)
var arrayPivot = array[pivot]; // pivot value
Swap(array, pivot, to - 1); // move pivot value to end for now, after this pivot not used
var newPivot = from; // new pivot
for (int i = from; i < to - 1; i++) // be careful to leave pivot value at the end
{
// Invariant: from <= newpivot <= i < to - 1 &&
// forall from <= j <= newpivot, array[j] <= arrayPivot && forall newpivot < j <= i, array[j] > arrayPivot
//if (array[i] <= arrayPivot)
if (array[i].CompareTo(arrayPivot) != -1)
{
Swap(array, newPivot, i); // move value smaller than arrayPivot down to newpivot
newPivot++;
}
}
Swap(array, newPivot, to - 1); // move pivot value to its final place
return newPivot; // new pivot
// Post: forall i <= newpivot, array[i] <= array[newpivot] && forall i > ...
}
public static void SequentialQuickSort<T>(T[] array) where T : IComparable<T>
{
SequentialQuickSort(array, 0, array.Length);
}
static void SequentialQuickSort<T>(T[] array, int from, int to) where T : IComparable<T>
{
if (to - from <= Threshold)
{
InsertionSort<T>(array, from, to);
}
else
{
int pivot = from + (to - from) / 2; // could be anything, use middle
pivot = Partition<T>(array, from, to, pivot);
// Assert: forall i < pivot, array[i] <= array[pivot] && forall i > ...
SequentialQuickSort(array, from, pivot);
SequentialQuickSort(array, pivot + 1, to);
}
}
public static void ParallelQuickSort<T>(T[] array) where T : IComparable<T>
{
ParallelQuickSort(array, 0, array.Length,
(int)Math.Log(Environment.ProcessorCount, 2) + 4);
}
static void ParallelQuickSort<T>(T[] array, int from, int to, int depthRemaining) where T : IComparable<T>
{
if (to - from <= Threshold)
{
InsertionSort<T>(array, from, to);
}
else
{
int pivot = from + (to - from) / 2; // could be anything, use middle
pivot = Partition<T>(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);
}
}
}
}
#endregion
}
@djmarcus1
Copy link

djmarcus1 commented Mar 30, 2020

Really nice code.

Some feedback:

[1] The methods should define T as IList<T> so it can sort arrays and List<T> collections, or any custom objects.

Ex:
public static void InsertionSort<T>(T[] array, int from, int to) where T : IComparable<T>, **IList<T>**

[2] Sorting should allow ascending or descending ordering. I don't see it in your implementation (perhaps I'm missing the obvious).

This is best done via allowing the programmer to specify an explicit comparator, so that the sort can be customized.
For all its worth, look at the 'Sort' method of List.

For ex:
Scores.Sort( (x, y) => -x.Value.CompareTo(y.Value));

Where Scores is a List<T> and T is an object that has a property Value

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment