Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

source code for Array.sort() method in dot net 2.0

Posted on 2007-11-16
2
Medium Priority
?
1,501 Views
Last Modified: 2013-11-07
I am testing various implementations of quicksort and a couple of other sorting routines in C#.
I am also comparing these to the internal dot net Array.sort() method.
The built in dotnet sorting function beats all the handcoded ones by a tiny margin over hundreds of millions of records.

I know that the dot net Array.sort method uses a 'tuned version of quicksort' but have no other information as to what it is doing. Since it does not choke on large sorted data sets, I assume it uses a median of three (or some other method of choosing a pivot point)  which I would think would make it slower than algorithms that expect unsorted data at all times but since my tests don't seem to prove that, I would like to see for myself what was done. It also works with different data types which implies more internal checking which implies a slower runtime than one that does not check but once again, my tests don't show that.

I imagine the code is posted online at Microsoft somewhere but I have not been able to find it.
Anyone that can show me the algorithm used by the internal dot net Array.sort() method gets 500 points.


thanks.

claysdna
0
Comment
Question by:clays_dna
2 Comments
 
LVL 37

Accepted Solution

by:
gregoryyoung earned 2000 total points
ID: 20303296
see reflector (disassembles the framework): http://www.aisto.com/roeder/dotnet/

source requested:


private void QuickSort<TValue>(T[] keys, TValue[] values, int left, int right, IComparer<T> comparer)
{
    do
    {
        int index = left;
        int num2 = right;
        T y = keys[index + ((num2 - index) >> 1)];
        do
        {
            try
            {
                while (comparer.Compare(keys[index], y) < 0)
                {
                    index++;
                }
                while (comparer.Compare(y, keys[num2]) < 0)
                {
                    num2--;
                }
            }
            catch (IndexOutOfRangeException)
            {
                throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", new object[] { y, y.GetType().Name, comparer }));
            }
            catch (Exception exception)
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), exception);
            }
            if (index > num2)
            {
                break;
            }
            if (index < num2)
            {
                T local2 = keys[index];
                keys[index] = keys[num2];
                keys[num2] = local2;
                if (values != null)
                {
                    TValue local3 = values[index];
                    values[index] = values[num2];
                    values[num2] = local3;
                }
            }
            index++;
            num2--;
        }
        while (index <= num2);
        if ((num2 - left) <= (right - index))
        {
            if (left < num2)
            {
                this.QuickSort<TValue>(keys, values, left, num2, comparer);
            }
            left = index;
        }
        else
        {
            if (index < right)
            {
                this.QuickSort<TValue>(keys, values, index, right, comparer);
            }
            right = num2;
        }
    }
    while (left < right);
}

 

 
0
 

Author Comment

by:clays_dna
ID: 20303513
thanks for fast response and thanks for cluing me in to reflector

clay
0

Featured Post

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Jaspersoft Studio is a plugin for Eclipse that lets you create reports from a datasource.  In this article, we'll go over creating a report from a default template and setting up a datasource that connects to your database.
High user turnover can cause old/redundant user data to consume valuable space. UserResourceCleanup was developed to address this by automatically deleting user folders when the user account is deleted.
The viewer will learn how to use and create keystrokes in Netbeans IDE 8.0 for Windows.
The viewer will learn how to use and create new code templates in NetBeans IDE 8.0 for Windows.

963 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question