ListComparisons.cs

void Main()
{
	const int listSize = 1000;
	const int sampleSize = 10000;
	
	var sortedList = Enumerable.Range(0,listSize).ToList();
	var unsortedList = new List<int>(sortedList);
		
	var sortedCount = 0;
	sortedList.Sort((l,r) => {sortedCount++; return l - r;});
	//sortedCount.Dump("Sorted");
	// Returns: 10519	

	var totalUnsortedComparisons = 0;
	for(var i = 0; i < sampleSize; i++)
	{
		var unsortedCount = 0;
		unsortedList.Shuffle();
		unsortedList.Sort((l,r) => {unsortedCount++; return l - r;});
		totalUnsortedComparisons += unsortedCount;
	}
	
	//(totalUnsortedComparisons / sampleSize).Dump("Unsorted");
	// Returns: 13547
}

public static class Extensions
{
	static Random rng = new Random();
	
	public static void Shuffle<T>(this IList<T> list)   
	{   
		// http://stackoverflow.com/a/1262619/1344760
		int n = list.Count;   
		while (n > 1) {   
			n--;   
			int k = rng.Next(n + 1);   
			T value = list[k];   
			list[k] = list[n];   
			list[n] = value;   
		}   
	}
}