Enumerable.SortBy - Which sorting function is used?

Question

Can anyone please tell me that which type of sorting technique (bubble, insertion, selection) is used in Linq.Sort by.

EDIT: Is there also an easy was to spe into this function and see the source myself - I used to be able to do that with Java

Answer 1

There is no LINQ Enumerable.SortBy method.

However, there is an Enumerable.OrderBy function which instantiates a new OrderedEnumerable that uses the EnumerableSorter class. The source code for these classes are below. You are welcome to call them whatever you like.

internal abstract class EnumerableSorter<TElement>
{
    // Methods
    protected EnumerableSorter()
    {
    }

    internal abstract int CompareKeys(int index1, int index2);
    internal abstract void ComputeKeys(TElement[] elements, int count);
    private void QuickSort(int[] map, int left, int right)
    {
        do
        {
            int index = left;
            int num2 = right;
            int num3 = map[index + ((num2 - index) >> 1)];
            do
            {
                while ((index < map.Length) && (this.CompareKeys(num3, map[index]) > 0))
                {
                    index++;
                }
                while ((num2 >= 0) && (this.CompareKeys(num3, map[num2]) < 0))
                {
                    num2--;
                }
                if (index > num2)
                {
                    break;
                }
                if (index < num2)
                {
                    int num4 = map[index];
                    map[index] = map[num2];
                    map[num2] = num4;
                }
                index++;
                num2--;
            }
            while (index <= num2);
            if ((num2 - left) <= (right - index))
            {
                if (left < num2)
                {
                    this.QuickSort(map, left, num2);
                }
                left = index;
            }
            else
            {
                if (index < right)
                {
                    this.QuickSort(map, index, right);
                }
                right = num2;
            }
        }
        while (left < right);
    }

    internal int[] Sort(TElement[] elements, int count)
    {
        this.ComputeKeys(elements, count);
        int[] map = new int[count];
        for (int i = 0; i < count; i++)
        {
            map[i] = i;
        }
        this.QuickSort(map, 0, count - 1);
        return map;
    }
}

internal class EnumerableSorter<TElement, TKey> : EnumerableSorter<TElement>
{
    // Fields
    internal IComparer<TKey> comparer;
    internal bool descending;
    internal TKey[] keys;
    internal Func<TElement, TKey> keySelector;
    internal EnumerableSorter<TElement> next;

    // Methods
    internal EnumerableSorter(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending, EnumerableSorter<TElement> next)
    {
        this.keySelector = keySelector;
        this.comparer = comparer;
        this.descending = descending;
        this.next = next;
    }

    internal override int CompareKeys(int index1, int index2)
    {
        int num = this.comparer.Compare(this.keys[index1], this.keys[index2]);
        if (num == 0)
        {
            if (this.next == null)
            {
                return (index1 - index2);
            }
            return this.next.CompareKeys(index1, index2);
        }
        if (!this.descending)
        {
            return num;
        }
        return -num;
    }

    internal override void ComputeKeys(TElement[] elements, int count)
    {
        this.keys = new TKey[count];
        for (int i = 0; i < count; i++)
        {
            this.keys[i] = this.keySelector(elements[i]);
        }
        if (this.next != null)
        {
            this.next.ComputeKeys(elements, count);
        }
    }
}

You can use .NET Reflector to read the source of compiled .NET assemblies.

Answer 2

After looking it up in reflector, the OrderBy LINQ operator uses quicksort.

internal abstract class EnumerableSorter<TElement>
{
    // Methods
    [TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")]
    protected EnumerableSorter();
    internal abstract int CompareKeys(int index1, int index2);
    internal abstract void ComputeKeys(TElement[] elements, int count);
    private void QuickSort(int[] map, int left, int right);
    internal int[] Sort(TElement[] elements, int count);
}

The method name QuickSort makes it fairly obvious, and the algorithm confirms it.

To inspect an assembly, use a tool like ILSpy (the usual name thrown around is reflector, however, that won't be free anymore in the next version, and all free versions contain a disable switch based on time, and the last free version will be disabled sometime in march 2011).

Answer 3

The documentation for Enumrable.OrderBy just states

This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved.

That means that the implementation might differ between different releases of .NET Framework, but assume it O(n log n).

Edit
Just to note, the documentation for Array.Sort explicitly mentions the use of quick sort (and notes that it is unstable).