Any multi-core sorting implementation in .NET?
3 Answers
Here's a multi-threaded QuickSort I put together a while back using async/await. Under a certain sort size, it "reverts" back to an elementary sort known as Double-Ended Selection Sort:
public static class SortExtensions
{
/// <summary>
/// Sorts the list.
/// </summary>
/// <typeparam name="T">
/// The IComparable element type of the list.
/// </typeparam>
/// <param name="list">The list to sort.</param>
public static async Task SortIt<T>(this IList<T> list) where T : IComparable<T> =>
await SortIt(list, 0, list.Count - 1);
/// <summary>
/// Sorts the list.
/// </summary>
/// <typeparam name="T">The element type of the list.</typeparam>
/// <param name="list">The list to sort.</param>
/// <param name="lowerbound">The lower bound.</param>
/// <param name="upperbound">The upper bound.</param>
private static async Task SortIt<T>(
this IList<T> list,
int lowerbound,
int upperbound) where T : IComparable<T>
{
// If list is non-existent or has zero or one element, no need to sort, so exit.
if ((list == null) || (upperbound - lowerbound < 1))
{
return;
}
const int MinListLength = 6;
if (upperbound - lowerbound > MinListLength)
{
await list.QuickSort(lowerbound, upperbound);
return;
}
await list.DoubleEndedSelectionSort(lowerbound, upperbound);
}
/// <summary>
/// QuickSorts the list.
/// </summary>
/// <typeparam name="T">The element type of the list.</typeparam>
/// <param name="list">The list to sort.</param>
/// <param name="lowerbound">The lower bound.</param>
/// <param name="upperbound">The upper bound.</param>
private static async Task QuickSort<T>(
this IList<T> list,
int lowerbound,
int upperbound) where T : IComparable<T>
{
int left = lowerbound;
int right = upperbound;
int middle = (lowerbound + upperbound) >> 1;
int pivotindex = (list[lowerbound].CompareTo(list[middle]) <= 0)
&& (list[middle].CompareTo(list[upperbound]) <= 0)
? middle
: ((list[middle].CompareTo(list[lowerbound]) <= 0)
&& (list[lowerbound].CompareTo(list[upperbound]) <= 0)
? lowerbound
: upperbound);
T pivotvalue = list[pivotindex];
do
{
while ((left < upperbound) && (list[left].CompareTo(pivotvalue) < 0))
{
left++;
}
while ((right > lowerbound) && (list[right].CompareTo(pivotvalue) > 0))
{
right--;
}
if (left > right)
{
continue;
}
(list[left], list[right]) = (list[right], list[left]);
left++;
right--;
}
while (right > left);
if (lowerbound < right)
{
await list.SortIt(lowerbound, right);
}
if (left < upperbound)
{
await list.SortIt(left, upperbound);
}
}
/// <summary>
/// Double-ended selection sorts the list.
/// </summary>
/// <typeparam name="T">The element type of the list.</typeparam>
/// <param name="list">The list to sort.</param>
/// <param name="lowerbound">The lower bound.</param>
/// <param name="upperbound">The upper bound.</param>
private static async Task DoubleEndedSelectionSort<T>(
this IList<T> list,
int lowerbound,
int upperbound) where T : IComparable<T>
{
// Initialize some working variables that will hold the sortable sublist indices.
int left = lowerbound;
int right = upperbound;
// Keep sorting the list while the upper bound of the sublist is greater than the lower bound.
while (right > left)
{
// Find get the indices of the smallest and largest elements of the sublist.
(int smallest, int largest) = await list.FindSmallestAndLargest(left, right);
if (smallest != largest)
{
// If they're different elements, swap the smallest with left element of the sublist.
(list[left], list[smallest]) = (list[smallest], list[left]);
if (largest == left)
{
// If the largest element of the sublist was the left element, then now, it has to be the
// smallest due to the swap.
largest = smallest;
}
}
if (largest != right)
{
// If the largest element of the sublist is the rightmost element, then they need to be swapped.
(list[right], list[largest]) = (list[largest], list[right]);
}
// Move the sublist search indices one in from the left and the right.
left++;
right--;
}
}
/// <summary>
/// Finds the smallest and largest list element indices.
/// </summary>
/// <typeparam name="T">The element type of the list.</typeparam>
/// <param name="list">The list to search.</param>
/// <param name="lowerbound">The lower bound.</param>
/// <param name="upperbound">The upper bound.</param>
private static async Task<(int, int)> FindSmallestAndLargest<T>(
this IList<T> list,
int lowerbound,
int upperbound) where T : IComparable<T>
{
int smallest = (list[lowerbound].CompareTo(list[upperbound]) < 0) ? lowerbound : upperbound;
int largest = (list[lowerbound].CompareTo(list[upperbound]) < 0) ? upperbound : lowerbound;
lowerbound++;
int loop = upperbound;
while (loop > lowerbound)
{
loop--;
if (list[loop].CompareTo(list[smallest]) < 0)
{
smallest = loop;
}
if (list[loop].CompareTo(list[largest]) > 0)
{
largest = loop;
}
}
return (smallest, largest);
}
}
10 Comments
fithu
Sometimes this code produces wrong results, you need to check it better.
Jesse C. Slicer
Really? Passes a pretty good battery of unit tests. Can you show a sample where it doesn't?
fithu
I sorted a set of pieces from source code files, and got this result:
fithu
(see selected lines on the picture): img600.imageshack.us/img600/9210/clipboard01j.png
Jesse C. Slicer
I can't see the entire column "Type" on the right, but it starts out as "SmartDif". I'd need to know how that type implements the IComparable interface to see why those two lines in particular would sort differently.
|
There is an interesting article on CodeProject which describes an algorithm using the TPL framework: