Solved

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

Posted on 2007-11-16
2
1,478 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 500 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

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

Introduction Hi all and welcome to my first article on Experts Exchange. A while ago, someone asked me if i could do some tutorials on object oriented programming. I decided to do them on C#. Now you may ask me, why's that? Well, one of the re…
Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
The viewer will learn how to use and create new code templates in NetBeans IDE 8.0 for Windows.

747 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now