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)

You might be interested in my related question. stackoverflow.com/questions/10110013/… — Tim Schmelter
– Tim Schmelter, Commented Apr 24, 2012 at 14:09
@TomaszSikora: You can simply sort by calling Array.Sort(people1), since the IComparable<T> implementation is used automatically. — Olivier Jacot-Descombes
– Olivier Jacot-Descombes, Commented Apr 24, 2012 at 14:13
I did notice something... Linq is faster when sorting bigger arrays. Array.Sort is faster when Array is less than 100 000 elements. Why is that happening? — Tomasz Sikora
– Tomasz Sikora, Commented Apr 24, 2012 at 14:41
The key thing to understand here is that the result of a query expression is a query. It is not the results of the query. Also: use Stopwatch for timing, not DateTime.Now. You will get results that are both more accurate and more precise. — Eric Lippert
– Eric Lippert, Commented Apr 24, 2012 at 14:46
Please use a stopwatch to get a more accurate reading for the time. stackoverflow.com/questions/28637/… — David Basarab
– David Basarab, Commented Dec 14, 2012 at 20:49

Botz3000 · Accepted Answer · 2012-04-24 14:05:52Z

57

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.

edited Apr 24, 2012 at 14:05

answered Apr 24, 2012 at 14:00

Botz3000

39.8k8 gold badges107 silver badges128 bronze badges

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

3 Comments

Steve Wellens Over a year ago

Code that doesn't execute will always out perform executing code!

Ben Lesh Over a year ago

I hope the OP doesn't feel silly. It's a very common issue/mistake I've seen (and probably have done myself): Not knowing or understanding when you're actually enumerating an IEnumerable and when you're just altering it. I think more common than this is the issue where you cost yourself efficiency by enumerating your IEnumerable multiple times.

Botz3000 Over a year ago

@blesh Yes, it surely isn't the first thing people get to know about Linq :)

Skiminok · Accepted Answer · 2012-04-24 14:01:19Z

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.

Adam Houldsworth · Accepted Answer · 2012-04-24 14:19:58Z

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();

Meonester · Accepted Answer · 2012-04-24 14:09:07Z

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.

Collectives™ on Stack Overflow

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

4 Answers 4

3 Comments

Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

Comments

Comments

Linked

Related