Are we allowed to OrderBy(Random)?

Question

I sometimes shuffle lists or arrays using OrderBy (item => R.NextDouble()), where Random R is initialized elsewhere.

Now this clearly is a hack, though the one recommended everywhere on this site, and it does work very nicely in practice.

However, it was also pointed out that this makes the assumption that the sorting algorithm does not get confused by changing values of a single item and e.g. enters an infinite loop.

My question is if there is some sort of implicit or explicit guarantee that this won't happen. I could not find anything about it in MSDN.

While there are very good, specialized O(n) algorithms for this purpose, I don't always want to search and copy-paste them in little side projects (we are not talking about prod here). They would obviously be the right solution.

Note that performance is not an issue at all. Also, there is no need for good or secure randomness (a cryptographic library must be used in that case) - this is just about shuffling stuff up a bit.

Answer 1

This is not guaranteed to work according to the documentation.

I have peeked into the internals. The sorting algorithm first captures all sort keys into a temporary array and then never calls them again. So in the current implementation this is safe. A new .NET version or even a patch can invalidate this technique.

You might argue that for compatibility reasons this will never change and the probably of that being true is like 95% (source: me). Microsoft has very high compat standards.

Another problem is that if you generate the same value for two keys they will not be positioned randomly. Instead, they will be positioned based on internals of the sorting algorithm which might be deterministic. For example, they might never switch their relative order.

I would only rely on this in short-term throw-away projects.

Another hack in this spirit is to sort by Guid.NewGuid(). That saves you another line of code and has no seeding problems. On the other hand guids might have a pattern or even be sequential. Also very problematic.

I would fail any of this in a code review of production code.