While running sort using Array.Sort() on an array of objects in .Net, I happened to use it with a compareTo since objects had some integers used for sort criterion. While writing this, I placed some diagnostic statements to see how many times compareTo was used. To my suprise, a mere 7 element array took 18 compares. I then replaced sort with a quicksort function which took 12 compares. Wanting to explore this further, I expanded test to double the number of elements and counted compares. Below is the output and code used to test this. At least 30% more comparisons are being made by .Net Array.Sort on average which is inefficient. Are better off writing our own sort?
------------------Console Output--------------------------------
.Net Array.Sort Hit Count for 10 elements: 48
Hand-written QSort Hit Count for 10 elements: 35
HitCount Diff: 13
Hit Count Fractional Increase: 27.08
.Net Array.Sort Hit Count for 20 elements: 163
Hand-written QSort Hit Count for 20 elements: 83
HitCount Diff: 80
Hit Count Fractional Increase: 49.08
.Net Array.Sort Hit Count for 40 elements: 359
Hand-written QSort Hit Count for 40 elements: 208
HitCount Diff: 151
Hit Count Fractional Increase: 42.06
.Net Array.Sort Hit Count for 80 elements: 848
Hand-written QSort Hit Count for 80 elements: 546
HitCount Diff: 302
Hit Count Fractional Increase: 35.61
.Net Array.Sort Hit Count for 160 elements: 1932
Hand-written QSort Hit Count for 160 elements: 1246
HitCount Diff: 686
Hit Count Fractional Increase: 35.51
.Net Array.Sort Hit Count for 320 elements: 4567
Hand-written QSort Hit Count for 320 elements: 3050
HitCount Diff: 1517
Hit Count Fractional Increase: 33.22
.Net Array.Sort Hit Count for 640 elements: 10778
Hand-written QSort Hit Count for 640 elements: 7120
HitCount Diff: 3658
Hit Count Fractional Increase: 33.94
.Net Array.Sort Hit Count for 1280 elements: 23410
Hand-written QSort Hit Count for 1280 elements: 15363
HitCount Diff: 8047
Hit Count Fractional Increase: 34.37
.Net Array.Sort Hit Count for 2560 elements: 50795
Hand-written QSort Hit Count for 2560 elements: 36584
HitCount Diff: 14211
Hit Count Fractional Increase: 27.98
.Net Array.Sort Hit Count for 5120 elements: 113708
Hand-written QSort Hit Count for 5120 elements: 78454
HitCount Diff: 35254
Hit Count Fractional Increase: 31
.Net Array.Sort Hit Count for 10240 elements: 248855
Hand-written QSort Hit Count for 10240 elements: 170283
HitCount Diff: 78572
Hit Count Fractional Increase: 31.57
.Net Array.Sort Hit Count for 20480 elements: 541349
Hand-written QSort Hit Count for 20480 elements: 389608
HitCount Diff: 151741
Hit Count Fractional Increase: 28.03
.Net Array.Sort Hit Count for 40960 elements: 1147178
Hand-written QSort Hit Count for 40960 elements: 746562
HitCount Diff: 400616
Hit Count Fractional Increase: 34.92
.Net Array.Sort Hit Count for 81920 elements: 2393047
Hand-written QSort Hit Count for 81920 elements: 1682768
HitCount Diff: 710279
Hit Count Fractional Increase: 29.68
.Net Array.Sort Hit Count for 163840 elements: 5129217
Hand-written QSort Hit Count for 163840 elements: 3705967
HitCount Diff: 1423250
Hit Count Fractional Increase: 27.75
.Net Array.Sort Hit Count for 327680 elements: 11312711
Hand-written QSort Hit Count for 327680 elements: 7635725
HitCount Diff: 3676986
Hit Count Fractional Increase: 32.5
.Net Array.Sort Hit Count for 655360 elements: 22918028
Hand-written QSort Hit Count for 655360 elements: 15814584
HitCount Diff: 7103444
Hit Count Fractional Increase: 31
--------------------Code used for this exercise is:-----------------------------------
using System;
using System.Text;
namespace SortTest
{
class Program
{
static MyInt[] data;
static void Main(string[] args)
{
int diff = 0;
double frac = 0.0;
for (int i = 10; i < 1000000; i *= 2)
{
buildData(i);
Array.Sort(data);
Console.WriteLine(".Net Array.Sort Hit Count for " + i.ToString() + " elements: " + hitCount.ToString());
int prevHitCount = hitCount;
hitCount = 0;
buildData(i);
qsort(ref data, 0, i - 1);
Console.WriteLine("Hand-written QSort Hit Count for " + i.ToString() + " elements: " + hitCount.ToString());
diff = prevHitCount - hitCount;
Console.WriteLine("HitCount Diff: " + diff.ToString());
frac = Math.Round((diff * 1.0/prevHitCount) * 100, 2);
Console.WriteLine("Hit Count Percent Diff: " + frac.ToString());
Console.WriteLine();
}
Console.ReadKey();
}
static void qsort(ref MyInt[] d, int l, int u)
{
if (l >= u)
return;
int m = l;
MyInt tmp = null;
for (int i = l + 1; i <= u; i++)
{
if (d[i].CompareTo(d[l]) > 0)
{
m++;
tmp = d[m];
d[m] = d[i];
d[i] = tmp;
}
}
tmp = d[l];
d[l] = d[m];
d[m] = tmp;
qsort(ref d, l, m);
qsort(ref d, m + 1, u);
}
static void buildData(int sz)
{
data = new MyInt[sz + 1];
Random r = new Random(sz);
int i = 0;
while (i < sz + 1)
{
data[i] = new MyInt();
data[i++].intVal = r.Next(sz);
}
}
static int hitCount;
class MyInt : IComparable
{
public int intVal = 0;
public int CompareTo(Object o)
{
hitCount++;
MyInt i = (MyInt)o;
return (i.intVal - this.intVal);
}
}
}
}