What is the algorithm used by sort() method on Array class in .NET?

Question

MSDN description for sort() method says :

Sorts the elements in an entire one-dimensional Array using the IComparable implementation of each element of the Array.

I checked IComparable but I didn't find any thing indicating which sort algorithm is being used.

I need to know how much the sort() method is parallel processing friendly.

Does anyone know what is the algorithm sort() method on Array class is using?

I need to know how much the sort() method is parallel processing friendly All the sort algorithms of .NET are single-threaded. — xanatos
– xanatos, Commented Mar 28, 2017 at 13:38
Link to a question asking for parallel sorting in .net: Parallel Sort Algorithm — xanatos
– xanatos, Commented Mar 28, 2017 at 14:01
@xanatos Thanks, I already know about sort algorithms and I also know that the best one which is designed to work in parrallel processing environment is Merge Sort , I just don't know what is the algorithm is being used in sort(), May please provide a reference for your first comment that says all of the sort algorithm in .NET are single-threaded ? and do you know anyother method other than sort() on Array that does the sorting? Thanks again — Rassam
– Rassam, Commented Mar 28, 2017 at 14:34
There are only four sorts in .NET that I know: Array.Sort (static), ArrayList.Sort (instance), List.Sort (instance), Enumerable.OrderBy (static, the LINQ OrderBy), so by knowing how they work I can know that they aren't parallelized... In general parallelizing is something VERY specialized, to be used only on VERY big collections. — xanatos
– xanatos, Commented Mar 28, 2017 at 14:36
You said, "I also know that the best one which is designed to work in parrallel processing environment is Merge Sort." How, pray tell, do you "know" that? Please point me at the reference. — Jim Mischel
– Jim Mischel, Commented Mar 29, 2017 at 2:44

Community · Accepted Answer · 2020-06-20 09:12:55Z

4

From the MSDN documentation:

This method uses the introspective sort (introsort) algorithm as follows:

If the partition size is fewer than 16 elements, it uses an insertion sort algorithm.

If the number of partitions exceeds 2 * LogN, where N is the range of the input array, it uses a Heapsort algorithm.

Otherwise, it uses a Quicksort algorithm.

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Mar 28, 2017 at 13:38

Justin Borromeo

1,3814 gold badges13 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Rassam Over a year ago

I didn't see that part of the documentation, thanks,

BanksySan · Accepted Answer · 2017-03-28 14:00:35Z

Here's a copy and paste:

public static void Sort(Array keys, Array items, int index, int length, IComparer comparer) {
    if (keys==null)
        throw new ArgumentNullException("keys");
    if (keys.Rank != 1 || (items != null && items.Rank != 1))
        throw new RankException(Environment.GetResourceString("Rank_MultiDimNotSupported"));
    if (items != null && keys.GetLowerBound(0) != items.GetLowerBound(0))
        throw new ArgumentException(Environment.GetResourceString("Arg_LowerBoundsMustMatch"));
    if (index < keys.GetLowerBound(0) || length < 0)
        throw new ArgumentOutOfRangeException((length<0 ? "length" : "index"), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
    if (keys.Length - (index - keys.GetLowerBound(0)) < length || (items != null && (index - items.GetLowerBound(0)) > items.Length - length))
        throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));

    Contract.EndContractBlock();

    if (length > 1) {
        if (comparer == Comparer.Default || comparer == null) {
            bool r = TrySZSort(keys, items, index, index + length - 1);
            if (r)
                return;
        }

        Object[] objKeys = keys as Object[];
        Object[] objItems = null;
        if (objKeys != null)
            objItems = items as Object[];
        if (objKeys != null && (items==null || objItems != null)) {
            SorterObjectArray sorter = new SorterObjectArray(objKeys, objItems, comparer);
            sorter.Sort(index, length);
        }
        else {
            SorterGenericArray sorter = new SorterGenericArray(keys, items, comparer);
            sorter.Sort(index, length);
        }
    }
}

You can get details from https://referencesource.microsoft.com/ though, the Array class is at: https://referencesource.microsoft.com/#mscorlib/system/array.cs,156e066ecc4ccedf

A very quick gander looks like it's not parallelisable.

Collectives™ on Stack Overflow

What is the algorithm used by sort() method on Array class in .NET?

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related