Solved

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

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

ScreenConnect 6.0 Free Trial

Want empowering updates? You're in the right place! Discover new features in ScreenConnect 6.0, based on partner feedback, to keep you business operating smoothly and optimally (the way it should be). Explore all of the extras and enhancements for yourself!

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
C# Single Form 8 42
Simple Injector with Web Service 4 40
InputLanguage 1 26
Expression Evaluater 3 24
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
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…
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
THe viewer will learn how to use NetBeans IDE 8.0 for Windows to perform CRUD operations on a MySql database.

770 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