Why is Array.Sort working faster after using Array.ForEach?

Question

I was spending my free time comparing built-in sorting algorithms in various libraries and languages and whe I hit C# and .NET I stumbled across a quite interesting and yet unknown to me "quirk". Here's the fist program I ran:

class Program { static void Main(string[] args) { var a = new int[1000000]; var r = new Random(); var t = DateTime.Now; for (int i = 0; i < 1000000; i++) { a[i] = r.Next(); } Console.WriteLine(DateTime.Now - t); t = DateTime.Now; Array.Sort(a); Console.WriteLine(DateTime.Now - t); Console.ReadKey(); } } 

and I got an average result of 11 ms for filling the array and 77 ms for sorting.

Then I tried this code:

class Program { static void Main(string[] args) { var a = new int[1000000]; var r = new Random(); var t = DateTime.Now; Array.ForEach(a, x => x = r.Next()); Console.WriteLine(DateTime.Now - t); t = DateTime.Now; Array.Sort(a); Console.WriteLine(DateTime.Now - t); Console.ReadKey(); } } 

and to my surprise the average times were 14 ms and 36 ms.

How can this be explained?

Answer 1

In the 2nd example, you are not assigning to the array items at all:

Array.ForEach(a, x => x = r.Next()); 

You're assigning to the lambda parameter x. Then, you're sorting an array consisting of zeros. This is probably faster because no data movement needs to happen. No writes to the array.

Apart from that, your benchmark methodology is questionable. Make the benchmark actually valid by: Using Stopwatch, increasing the running time by 10x, using Release mode without debugger, repeating the experiment and verifying the times are stable.

Answer 2

Because in the second case you do not really initialize an array and it remains all zeroes. In other words it is already sorted.

ForEach does not change entries