Solved

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

Posted on 2007-11-16
1,478 Views
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
Question by:clays_dna

LVL 37

Accepted Solution

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

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

clay
0

## Featured Post

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.