In the List<T>.Sort() method, is an item ever compared to itself?

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.

Fanchet

Sure, if the List<> contains the same object more than once. – Lebna

@Hans: Yeah, got confused a bit in my deleted comment. I was working with a list that contained instances of a class. Of course, in some programs, it can also be possible for the same instance to occur multiple times in the list. But as edited, I was wondering the case where the list contained distinct instances of the class. – Fanchet

I stand corrected. The comment in the Reference Source says: pre-sort the low, middle (pivot), and high values in place. This improves performance in the face of already sorted data, or data that is made up of multiple sorted runs appended together. – Lebna

Whether it is possible or not, you must support it because it is part of the contract for a comparison function. – Lillie

Answer 1

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)

Flea

Hmm.. yeah. Added a Console.WriteLine() at the start of the Compare() method. Compare(2,2) is called twice for the given list. – Fanchet

Confirmed using Mono 2.6.7.0. (I took the liberty of adding using directives and a WriteLine statement, to make it easier for folks to try for themselves.) – Talkathon

This no longer happens (identical C# code to yours above) with .NET 4.6.2. Now it writes just: Compare(1, 2) Compare(1, 3) Compare(2, 3) Efficient. – Abolish

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.

Talkathon

How does this explain JohnD's answer? Am I missing something obvious? – Fanchet

This answer keeps going getting voted up and up v__v. Can someone confirm the quicksort behaviour stated here, which seems to be contradicting JohnD's sample program? – Fanchet

Hmm, that's interesting! I'm glad that both answers appear near the top, now that JohnD's has been accepted. In that case, we must conclude that the docs are wrong. – Talkathon

There are many implementations of QuickSort, some of which compare elements against themselves. There is nothing wrong with the docs. – Lillie

I stand corrected -- I'd never seen QuickSort being written that way. However, I do maintain that the docs are wrong in calling this implementation detail out as being a part of the specification, which it is not. Any worst-case-quadratic, average-case-nlogn algorithm can be used as the sort function. – Talkathon

Answer 3

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).

Absinthism

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.

Talkathon