Why is Array.Sort() so slow compared to LINQ?

Question

I made quick testing application to compare LINQ sorting to Array.Sort on my custom objects. Array.Sort seems extremely slow!

I made my custom class like this:

class Person : IComparable<Person>
{
    public int Age { get; set; }
    public string Name { get; set; }

    public int CompareTo(Person obj)
    {
        return this.Age.CompareTo(obj.Age);
    }

    public Person()
    { }

}

Then i made my testing persons in main() :

string name = "Mr. Tomek";

Random r = new Random();
int size = 10000000;

DateTime start, end;
Person[] people1 = new Person[size];
Person[] people2 = new Person[size];

for (int i = 0; i < size; i++)
{
     people1[i] = new Person();
     people1[i].Age = r.Next(0, 10000);
     people1[i].Name = name;

     people2[i] = new Person();
     people2[i].Age = people1[i].Age;
     people2[i].Name = people1[i].Name;
}

After that i have measured time taken to Sort by Array.Sort and by LINQ:

start = DateTime.Now;
var sort = from s in people2
           orderby s.Age
           select s;
end = DateTime.Now;
Console.WriteLine("LINQ: ");
Console.WriteLine((end - start).TotalMilliseconds);

start = DateTime.Now;
Array.Sort(people1,((Person p1, Person p2)=>{return p1.CompareTo(p2);}));
end = DateTime.Now;

Console.WriteLine("IComparable: ");
Console.WriteLine((end - start).TotalMilliseconds);

Console.ReadLine();

Linq time: about 1 or 2 miliseconds

Array.Sort: over 16 SECONDS!

All arrays are sorted (LINQ produces new collection and leaves oryginal array unsorted) but Array.Sort is extremely slow! How could it be explained? (in DEBUG and RELEASE mode Array.Sort fails extremely)

I pasted code with lambda expression when sorting with Array.Sort but it's the same with and without it. (Class Person implements IComparable interface)

Answer 1

Your Linq query doesn't even get executed because you don't get the results. That's called deferred execution. The query is only executed when you actually enumerate over the results.

Use something like var results = sort.ToArray() to execute the query, then you will get more accurate results.

Answer 2

LINQ is lazy. Your people2 hasn't actually been sorted, LINQ just created a temporary "promise object" that it would be sorted. To make it actually happen, you have to force the evaluation by Console.WriteLine the sorted result, convert it into list/array or do anything else like this.

See more: deferred execution.

Answer 3

Linq statements return IEnumerable<T> or flavours of, this (or anything using the yield keyword) only executes when you iterate it. Most actions available from the Linq libraries (not all) are lazy / deferred.

You are not iterating it, so you are not actually performing the sort.

You need to force a full iteration. Sticking the results in a List will fully iterate the returned enumerable:

var sort = (from s in people2
            orderby s.Age
            select s).ToList();

Only then will you be comparing apples to apples.

In fact, in the case of a sort (orderby), simply selecting the first item will cause a full iteration as a sort needs to be done fully before you can return the first result:

var sort = from s in people2
           orderby s.Age
           select s;

var s = sort.First();

Answer 4

Try to change this part and do your test once again.

    start = DateTime.Now;
    var sort = (from s in people2
               orderby s.Age
               select s).ToList();
    end = DateTime.Now;

This will evaluate LINQ expression.