Solved

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

Posted on 2007-11-16
2
1,488 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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

 Watch the Recording: Learning MySQL 5.7

MySQL 5.7 has a lot of new features. If you've dabbled with an older version of MySQL, it is definitely worth learning.

Question has a verified solution.

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

It was really hard time for me to get the understanding of Delegates in C#. I went through many websites and articles but I found them very clumsy. After going through those sites, I noted down the points in a easy way so here I am sharing that undeā€¦
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 synchronize PHP projects with a remote server in NetBeans IDE 8.0 for Windows.

635 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