3

Any multi-core sorting implementation in .NET?

3 Answers 3

3

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);
    }
}
Sign up to request clarification or add additional context in comments.

10 Comments

Sometimes this code produces wrong results, you need to check it better.
Really? Passes a pretty good battery of unit tests. Can you show a sample where it doesn't?
I sorted a set of pieces from source code files, and got this result:
(see selected lines on the picture): img600.imageshack.us/img600/9210/clipboard01j.png
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.
|
2

Check this parallel extensions version of quicksort from a previous answer.

Comments

0

There is an interesting article on CodeProject which describes an algorithm using the TPL framework:

http://www.codeproject.com/KB/recipes/parallelSort.aspx.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.