0

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?

Rassam
  • 30
  • 8
  • 1
    *I need to know how much the sort() method is parallel processing friendly* All the sort algorithms of .NET are single-threaded. – xanatos Mar 28 '17 at 13:38
  • Link to a question asking for parallel sorting in .net: [Parallel Sort Algorithm](http://stackoverflow.com/q/1897458/613130) – xanatos Mar 28 '17 at 14:01
  • 1
    @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 Mar 28 '17 at 14:34
  • 1
    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 Mar 28 '17 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 Mar 29 '17 at 02:44
  • @JimMischel Sorry for the delay, Wikipedia : Merge sort parallelizes well due to use of the divide-and-conquer method. Several parallel variants are discussed in the third edition of Cormen, Leiserson, Rivest, and Stein's Introduction to Algorithms.[11] The first of these can be very easily expressed in a pseudocode with fork and join keywords https://en.m.wikipedia.org/wiki/Merge_sort#CITEREFCormenLeisersonRivestStein2009 – Rassam Apr 18 '17 at 19:06
  • @JimMischel This page has a brief introduction on different sort algorithms and you may find a comparative table between sort methods in this page, interesting. https://en.m.wikipedia.org/wiki/Sorting_algorithm – Rassam Apr 18 '17 at 19:11
  • I'm familiar with sorting algorithms, and with the benefits of parallel merge sort. I'll agree that it's a good option. Perhaps best in many situations, but to say unequivocally that one algorithm is "the best" is overstating things. – Jim Mischel Apr 18 '17 at 19:34

2 Answers2

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.

Community
  • 1
  • 1
Justin Borromeo
  • 1,201
  • 3
  • 13
  • 26
1

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.

BanksySan
  • 27,362
  • 33
  • 117
  • 216