In LINQ, does orderby() execute the comparing function only once or execute it whenever needed?

Question

I found a method to shuffle an array on the internet.

Random rand = new Random();
shuffledArray = myArray.OrderBy(x => rand.Next()).ToArray();

However, I am a little concerned about the correctness of this method. If OrderBy executes x => rand.Next() many times for the same item, the results may conflict and result in weird things (possibly exceptions).

I tried it and everything is fine, but I still want to know whether this is absolutely safe and always works as expected, and I can't find the answer by Google.

Could anyone give me some explanations?

Thanks in advance.

Answer 1

Your approach should work but it is slow.

It works because OrderBy first calculates the keys for every item using the key selector, then it sorts the keys. So the key selector is only called once per item.

In .NET Reflector see the method ComputeKeys in the class EnumerableSorter.

this.keys = new TKey[count];
for (int i = 0; i < count; i++)
{
    this.keys[i] = this.keySelector(elements[i]);
}
// etc...

whether this is absolutely safe and always works as expected

It is undocumented so in theory it could change in future.

For shuffling randomly you can use the Fisher-Yates shuffle. This is also more efficient - using only O(n) time and shuffling in-place instead of O(n log(n)) time and O(n) extra memory.

Related question

• C#: Is using Random and OrderBy a good shuffle algorithm?

Answer 2

I assume that you're talking about LINQ-to-Objects, in which case the key used for comparison is only generated once per element. (Note that this is just a detail of the current implementation and could change, although it's very unlikely to because such a change would introduce the bugs that you mention.)

To answer your more general question: your approach should work, but there are better ways to do it. Using OrderBy will typically be O(n log n) performance, whereas a Fisher-Yates-Durstenfeld shuffle will be O(n).

(There's an example Shuffle extension for IEnumerable<T> here, or an in-place equivalent for IList<T> here, if you prefer.)