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?

First, 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. — usr
– usr, Commented Mar 23, 2014 at 11:10

usr · Accepted Answer · 2014-03-23 11:12:10Z

8

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.

answered Mar 23, 2014 at 11:12

usr

172k38 gold badges251 silver badges380 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

demos_kratos Over a year ago

Thanks a lot. I didn't even bother checking the array. And I'll be using Stopwatch from now on. I used it now and the results were the same. And It was running in Release.

Denis Itskovich · Accepted Answer · 2014-03-23 11:12:06Z

3

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

answered Mar 23, 2014 at 11:12

Denis Itskovich

4,5533 gold badges35 silver badges56 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related