I came across something rather interesting the other day when trying to determine what sorting algorithms .Net Framework uses in its list class: The built-in sorting method runs much faster than the reverse-engineered and then compiled code, even though in theory the code being executed is identical.Using Lutz Roeder’s .Net Reflector, I was able to determine that QuickSort is used when List.Sort() is called.
Here is the generic QuickSort (I have left out some error handling portion) method that .Net 2.0 uses within it’s framework:
internal class ArraySortHelper<T>
{
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
{
while (comparer.Compare(keys[index], y) < 0)
{
index++;
}
while (comparer.Compare(y, keys[num2]) < 0)
{
num2—;
}
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);
}
public void Sort(T[] items, int index, int length, IComparer<T> comparer)
{
this.Sort<object>(items, null, index, length, comparer);
}
public virtual void Sort<TValue>(T[] keys, TValue[] values, int index, int length, IComparer<T> comparer)
{
if ((comparer == null) || (comparer == Comparer<T>.Default))
{
comparer = Comparer<T>.Default;
}
this.QuickSort<TValue>(keys, values, index, index + (length – 1), comparer);
}
}
Out of curiosity, I ran the following methods to determine the approximate time required when sorting 2,000,000 random numbers:
class Program
{
public void Test1()
{
List<int> l = new List<int>();
Random r = new Random();
for (int i = 0; i < 20000000; i++)
{
l.Add(r.Next());
}
DateTime t1 = DateTime.Now;
Console.Write("1…");
l.Sort();
TimeSpan t = DateTime.Now – t1;
Console.WriteLine(string.Format("{0} seconds." , t.Seconds));
}
public void Test2()
{
int[] n = new int[20000000];
Random r = new Random();
for (int i = 0; i < 20000000; i++)
{
n[i] = r.Next();
}
ArraySortHelper<int> qSort = new ArraySortHelper<int>();
DateTime t1 = DateTime.Now;
Console.Write("2…");
qSort.Sort(n, 0, n.Length – 1, null);
TimeSpan t = DateTime.Now – t1;
Console.WriteLine(string.Format("{0} seconds.", t.Seconds));
}
static void Main(string[] args)
{
Program p = new Program();
p.Test1();
p.Test2();
}
}
In the code above, Test1() calls the Sort() method within List class and Test2() calls the revere-engineered QuickSort() directly. The code is compiled with csc /o+ so that it is optimized. The result is rather interesting: Test1() used a bit more than 3 seconds to complete but Test2() used more than 9 second to complete! Even though in theory Test2() and Test1() should be approximately identical in terms of performance since they both invoke the same underlying QuickSort() method. The only explanation I have is that Microsoft has optimized its Framework code more than the framework itself can achieve (e.g. using some advanced tools that are only available to Microsoft).
If the above code is run under Mono, the result is exact the opposite: Test2() runs almost twice as fast as Test1(), finishing in roughly 10 seconds (Mono runs the same .Net code much slower than Microsoft’s implementation). My guess is that since Mono developers develop their framework code independently, the sorting algorithm used in Mono might be slightly less efficient than Microsoft’s version of QuickSort(), so there is no surprise there.
