Why does using Random in Sort causing [Unable to sort IComparer.Compare error]

Question

I tried shuffling a list of byte (List) using either code:

myList.Sort((a, b) => this._Rnd.Next(-1, 1));

or

myList.Sort(delegate(byte b1, byte b2)
{
    return this._Rnd.Next(-1, 1);
});

and they threw the following error:

Unable to sort because the IComparer.Compare() method returns inconsistent results. Either a value does not compare equal to itself, or one value repeatedly compared to another value yields different results. x: '{0}', x's type: '{1}', IComparer: '{2}'.

What is wrong with using a random rather than the compare function of byte?

I tried using LINQ function instead and it works.

var myNewList = myList.OrderBy(s => Guid.NewGuid());
var myNewList = myList.OrderBy(s => this._Rnd.NextDouble());

I did read that these methods are slower than Fisher–Yates shuffle giving O(n) runtime only. But was just wondering on using the Sort function and random.

Answer 1

Not only is the comparison relation required to be consistent, it is also required to impose a total ordering. For example, you cannot say "socks are smaller than shoes, shirts are neither smaller than nor greater than trousers" blah blah blah, feed that into a sort algorithm and expect to get a topological sort out of the other end. Comparison sorts are called comparison sorts because they require a well-formed comparison relation. In particular, quicksort can run forever or give nonsensical results if the comparison relation is not consistent, transitive, and total-ordering.

If what you want is a shuffle then implement a Fischer-Yates shuffle. (Do it correctly; even though the algorithm is trivial, it is almost always implemented wrong.) If what you want is a topological sort then implement a topological sort. Use the right tool for the job.

Answer 2

Because as the error says, Random is not consistent. You must have a comparer that always returns the same result when given the same parameters. otherwise the sort will not be consistent.

Knuth has a random sort algorithm which worked like an insertion sort, but you swapped the value with a randomly chosen location in hhe existing array.