In the List.Sort() method, is an item ever comp

Question

If I pass in a custom IComparer to an instance of a List's Sort() method, will the comparer's Compare(x,y) method ever be called with the same item?

ie. Is it possible that Compare(x,x) may be called.

Edit: More interested in the case where items of the list are distinct.

Answer 1

Although it's not strictly guaranteed, I'm pretty sure List's Sort method will never call your compare method to compare an object to itself unless that object happens to appear in the list multiple times. I base this conclusion on the fact that List.Sort is implemented using the QuickSort algorithm (according to MSDN), which never compares usually does not involve comparing the same element to itself (and neither do any of the othe documented sorting algorithms I can think of). (Edit: It seems that Microsoft's implementation does compare the element to itself. See accepted answer above.)

However, good coding practice would dictate that your IComparer implementation should be able to handle being passed the same object in both parameters, as otherwise your implementation is not fullfilling the contract defined by IComparer. It would probably work for your scenario, but you'd be relying on implementation details of the sort method (which might change in the future), and you wouldn't be able to use you IComparer implementation in other scenarios where there is no such guarantee (or worse, you or someone else DOES use it and possibly creates a difficult to find bug).

Answer 2

From the docs:

This method uses Array.Sort, which uses the QuickSort algorithm.

QuickSort will never compare an item to itself. Some implementations of QuickSort compare items to themselves. This can also happen if that item occurs more than once in your List.

Either way, in order for your comparison function to be a proper, well-behaved comparison function, you need to handle the case of elements being compared to themselves.

Answer 3

I wrote a test program to try it out. It looks like it actually does Compare() the same element to itself (at least Compare() is called for the same item twice). In this program, Compare() is called with arguments (2, 2).

using System;
using System.Collections.Generic;

static class Program
{
    class MyComparer : Comparer<int>
    {
        public override int Compare(int x, int y)
        {
            Console.WriteLine("Compare(" + x + ", " + y + ")");
            if (x < y) return -1;
            if (x > y) return 1;
            return 0;
        }
    }

    static void Main()
    {
        MyComparer comparer = new MyComparer();
        List<int> list = new List<int> { 1, 2, 3 };
        list.Sort(comparer);
        return;

    }
}

And the output is:

Compare(1, 2)
Compare(1, 3)
Compare(2, 3)
Compare(1, 2)
Compare(2, 2)
Compare(2, 3)
Compare(2, 2)

Answer 4

Another answer, this one based on the XML part of ECMA-335, the specification of the BCL (Base Class Library). Although not guaranteed to relate to what actual implementations do, this is as authoritative as it gets. And the spec states nothing but:

At worst, this operation is O(n^2), where n is the number of elements to sort. On average it's O(n log n).

Though this is suggestive of QuickSort, it is absolutely no guarantee. Nor does the spec require implementation in terms of Array.Sort.

Bottom line: as far as the spec is concerned, it is perfectly okay for implementations to compare items to themselves.