Is using Random and OrderBy a good shuffle algorithm?

Question

I have read an article about various shuffle algorithms over at Coding Horror. I have seen that somewhere people have done this to shuffle a list:

var r = new Random();
var shuffled = ordered.OrderBy(x => r.Next());

Is this a good shuffle algorithm? How does it work exactly? Is it an acceptable way of doing this?

Answer 1

It's not a way of shuffling that I like, mostly on the grounds that it's O(n log n) for no good reason when it's easy to implement an O(n) shuffle. The code in the question "works" by basically giving a random (hopefully unique!) number to each element, then ordering the elements according to that number.

I prefer Durstenfield's variant of the Fisher-Yates shuffle which swaps elements.

Implementing a simple Shuffle extension method would basically consist of calling ToList or ToArray on the input then using an existing implementation of Fisher-Yates. (Pass in the Random as a parameter to make life generally nicer.) There are plenty of implementations around... I've probably got one in an answer somewhere.

The nice thing about such an extension method is that it would then be very clear to the reader what you're actually trying to do.

EDIT: Here's a simple implementation (no error checking!):

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    // Note i > 0 to avoid final pointless iteration
    for (int i = elements.Length-1; i > 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        int swapIndex = rng.Next(i + 1);
        T tmp = elements[i];
        elements[i] = elements[swapIndex];
        elements[swapIndex] = tmp;
    }
    // Lazily yield (avoiding aliasing issues etc)
    foreach (T element in elements)
    {
        yield return element;
    }
}

EDIT: Comments on performance below reminded me that we can actually return the elements as we shuffle them:

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    for (int i = elements.Length - 1; i >= 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        // ... except we don't really need to swap it fully, as we can
        // return it immediately, and afterwards it's irrelevant.
        int swapIndex = rng.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
    }
}

This will now only do as much work as it needs to.

Note that in both cases, you need to be careful about the instance of Random you use as:

• Creating two instances of Random at roughly the same time will yield the same sequence of random numbers (when used in the same way)
• Random isn't thread-safe.

I have an article on Random which goes into more detail on these issues and provides solutions.