Internal working of the Sort() and CompareTo() met

Question

I've been trying to figure out how the CompareTo() method works internally and I failed. I've searched this site and read some posts, and I think I've seen all there is to see in MSDN about this subject and I just don't seem to get it. An MSDN example:

public int CompareTo(object obj)
{
    if (obj == null)
    {
        return 1;
    }

    Temperature otherTemperature = obj as Temperature;
    if (otherTemperature != null)
    {
        return this.temperatureC.CompareTo(otherTemperature.temperatureC);
    }
    else
    {
        throw new ArgumentException("the object is not a temperature");
    }
}

This is the MSDN example of the implementation of the CompareTo() method. I understand this, I understand how the IComparable interface works, if I understood correctly this gets called when I use the ArrayList.Sort() method.

What I don't understand is: when does the program pass the argument for the CompareTo(object obj) method? Or in other words, how does the Sort() method work? I mean, this code is comparing the instance of a temperature with another instance of temperature, but when or how is the program getting the second temperature instance for the comparison to take place? I hope my question makes sense.

I've tried printing to the screen the CompareTo() process so maybe I could reverse-engineer the output but I confused myself even more.

EDIT: Maybe if I go step by step I can explain myself better. Suppose I have 3 temperatures objects: 34, 45, 21 in an ArrayList. When I call ArrayList.Sort(), is the CompareTo() method called like 34.CompareTo(45)? And then 45.CompareTo(21)? The returned integers would be 1 in the first comparison and -1 in the second? And how did those integers get returned if I only defined the CompareTo() method to return 1 only if the obj (the parameter) was null? I didn't define anything to return -1 or 0. It's as if I was implementing a method that's already been implemented. Defining a CompareTo() method when it's already defined to return -1, 0 and 1.

Answer 1

The sorting method is independent of the CompareTo method. I'm not sure what sorting algorithm is used but I'd guess it's something like a quick sort (obv not a bubble sort). If you're interested in those algorithms Wikipedia documents them in detail.

The CompareTo method is simply a means to compare objects of the same type. It's defined for many of the common .NET types to begin with and can be overriden to do comparisons between custom objects (things you create). Basically you call it from an object of type A passing it a second object of type A and the return value indicates if the two are equal or if one is greater than the other.

It's best to think of CompareTo as a utility function. It exists so you can do custom comparisons using the sorting methods provided with common .NET data structures. Without something like it, you would have to write the sorting algorithm yourself in order to compare types that you've created. It's purpose is simply to make sorting methods reusable/extensible.

Answer 2

There are different sort algorithms. However, no matter what there are points where an algorithm must decide which element is greater, which is when CompareTo is called.

a.CompareTo(b) < 0;

If a and b are Integers (or in pseudocode), you could also use:

a < b

I think you will find the a < b notation in a lot of pseudocode or integer sort algorithm examples. CompareTo method of IComparable<T> is an object-oriented implementation - or notation.

Answer 3

When you want to compare a to b, you say:

int result=a.CompareTo(b);

ie, the first comparison operand is this and the second one is the parameter passed to the function.

Then when you sort the array, regardless of the algorithm used you have to compare elements together, sending them as this and obj to object.CompareTo (or viable overloads of this function).

Answer 4

Let's start with the basic idea.

What is the purpose of CompareTo?

What is 42 to 1337. Is 42... greater than, less than or equal to 1337?

This question and its answer are modeled by the CompareTo method in the IComparable<T> and IComparable interfaces. For A.CompareTo(B), the method can return:

• A is greater than B: an integer value greater than 0.
• A is less than B: an integer value less than 0.
• A is equal to B: an integer value equal to 0.

And of course, IComparable is not limited to integers. You can implement IComparable to compare any two objects that you think should be comparable. For example, strings:

What is "Armadillo" to "Zodiac": Is "Armadillo"... greater than, less than or equal to "Zodiac"?

The answer depends on your definition of greater than, less than and equal to. For strings the usual order is that a word that would occur later in the dictionary is greater than a word that occurs earlier.

How does CompareTo help sorting?

Okay, now you know how you can compare any two objects. This is useful for many algorithms, but mostly sorting and ordering algorithms. Take for example a very simple sorting algorithm: stupid sort. The idea is:

Look at two adjacent elements in your array, A and B.
When A <= B: go forward to the next pair.
When A > B: swap A and B, and go back to the previous pair.
When we reach the end, we're done.

You see, to get sorted there must be a way to determine which of the two elements is the greater one. That's where IComparable<T> comes into play.

public static void StupidSort<T>(T[] array)
            where T : IComparable<T>
{
    int index = 0;
    while (index < array.Length)
    {
        if (index == 0 ||
            array[index - 1].CompareTo(array[index]) <= 0)
        {
            index++;
        }
        else
        {
            Swap(array, index - 1, index);
            index--;
        }
    }
}

What happens when CompareTo would always return 1?

You can of course program CompareTo to return anything you want. But if you screw up, then your method no longer answers the question what is this to obj? Always returning a 1 would mean that for any A and B, A is always greater than B. That's like saying: 20 is greater than 10 and 10 is greater than 20. It does not make sense, and the result is that any sorting you do will also not make any sense. Garbage in... garbage out.

The rules of the game are, for three given objects A, B and C:

• A.CompareTo(A) must return 0 (A is equal to A).
• If A.CompareTo(B) returns 0, then B.CompareTo(A) returns 0 (If A is equal to B, then B is equal to A).
• If A.CompareTo(B) returns 0, and B.CompareTo(C) returns 0, then A.CompareTo(C) returns 0 (If A is equal to B, and B is equal to C, then A is equal to C).
• If A.CompareTo(B) returns a value greater than 0, then B.CompareTo(A) returns a value less than 0 (If A is greater than B, then B is less than A).
• If A.CompareTo(B) returns a value less than 0, then B.CompareTo(A) returns a value greater than 0 (If A is less than B, then B is greater than A).
• If A.CompareTo(B) returns a value greater than 0, and B.CompareTo(C) returns a value greater than 0, then A.CompareTo(C) returns a value greater than 0 (If A is greater than B, and B is greater than C, then A is greater than C).
• If A.CompareTo(B) returns a value less than 0, and B.CompareTo(C) returns a value less than 0, then A.CompareTo(C) returns a value less than 0 (If A is less than B, and B is less than C, then A is less than C).
• null is always less than any non-null object.

If your implementation doesn't adhere to these (simple and logical) principles, then sorting algorithms can literally do anything, and probably don't give the results you expect.

Answer 5

In short, Sort takes two elements of your ArrayList, and calls CompareTo for the first elements, and pass second element as an argument, like this:

element1.CompareTo(element2)

CompareTo returns negative value if element1 is less that element2, 0 if they are equal, positive value otherwise. Sort uses this return value to, uhm, do some sorting. Then it repeats this process for next two elements, does some more sorting, and so on until ArrayList is sorted. Search for "sorting algorithm" to get more info about this process.