When will a Comparer make Sort throw an ArgumentException?

Question

The documentation for Sort says that Sort will throw an ArgumentException if "The implementation of comparer caused an error during the sort. For example, comparer might not return 0 when comparing an item with itself."

Apart from the example given, can anyone tell me when this would otherwise happen?

Stallings

Answer 1

The sort algorithm (QuickSort) relies on a predictable IComparer implementation. After a few dozen layers of indirection in the BCL you end up at this method:

public void Sort(T[] keys, int index, int length, IComparer<T> comparer)
{
    try
    {
        ...
        ArraySortHelper<T>.QuickSort(keys, index, index + (length - 1), comparer);

    }
    catch (IndexOutOfRangeException)
    {
        ...
        throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", values));
    }
}

Going a bit further into the QuickSort implementation, you see code like this:

    while (comparer.Compare(keys[a], y) < 0)
    {
        a++;
    }
    while (comparer.Compare(y, keys[b]) < 0)
    {
        b--;
    }

Basically if the IComparer misbehaves the Quicksort call with throw an IndexOutOfRangeException, which is wrapped in n ArgumentException.

Here is another example of bad IComparer's

class Comparer: IComparer<int>
{
    public int Compare(int x, int y)
    {
        return -1;
    }
}

So I guess, the short answer is, anytime your IComparer implementation does not consistently compare values as defined in the documentation:

Compares two objects and returns a value indicating whether one is less than, equal to or greater than the other.

Sympetalous

Thanks - that's pretty much how far I made it before turning to SO. The original error seems to be an IndexOutOfRangeException. How is that related to the predicability of the comparer? – Stallings

Okay - with that I can see where that may be a problem. Thanks! – Stallings

I've looked into this a bit more. If I'm not mistaken the comparer can be pretty flaky most of the time. It is only when the index above would go beyond the boundaries of the array the problem occurs. Obviously this is hardly useful as the comparer should just do the right thing. – Stallings

Answer 2

I ran into this today, and after investigating, I found that sometimes my comparer was being called with x and y being references to the same object, and my comparer was not returning 0. Once I fixed that, I stopped getting the exception.

HTH,

Eric

Vaporing

Great point Eric, I think this is exactly the issue I've got involved into. Many thanks for your help! – Electroform