Вот многопоточная быстрая сортировка, которую я собрал некоторое время назад, используя async / await. При определенном размере сортировки он «возвращается» к элементарной сортировке, известной как сортировка с двойным завершением:
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);
}
}