Comparison method for sorting that shuffles equal elements randomly

Question

Here's a puzzle for you.

I want to change the following comparison method, so that when two items are considered equal, they will be shuffled randomly.

myList.Sort( (x, y) => x.Score.CompareTo(y.Score) );

I could imagine that this scenario would be useful when ordering search results if you didn't want to give preference to one result over another when their scores are the same.

Anyone want to give it a go?

Here was my first attempt at a solution, but it doesn't work. I'll let you figure out why.

class RandomizeWhenEqualComparer<T> : IComparer<T>
{
    private readonly Func<T, T, int> _comparer;

    public int Compare(T x, T y)
    {
            if (x.Equals(y)) return 0;

        int result = _comparer(x, y);

        if (result != 0) return result;

        double random = StaticRandom.NextDouble();
        return (random < .5) ? -1 : 1;
    }

    public RandomizeWhenEqualComparer(Func<T, T, int> comparer)
    {
        _comparer = comparer;
    }
}

Answer 1

First shuffle it randomly, then use a stable sort.