Expiring Today—Celebrate National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

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

Posted on 2007-11-16
2
Medium Priority
?
1,494 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 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

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

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

This article is for Object-Oriented Programming (OOP) beginners. An Interface contains declarations of events, indexers, methods and/or properties. Any class which implements the Interface should provide the concrete implementation for each Inter…
The article shows the basic steps of integrating an HTML theme template into an ASP.NET MVC project
The viewer will learn how to use NetBeans IDE 8.0 for Windows to connect to a MySQL database. Open Services Panel: Create a new connection using New Connection Wizard: Create a test database called eetutorial: Create a new test tabel called ee…
The viewer will learn how to synchronize PHP projects with a remote server in NetBeans IDE 8.0 for Windows.

719 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