How does CompareTo method work while Implementing IComparable?

Question

I have a class:

 public class Customer :IComparable<Customer>
        {
            public int Id { get; set; }
            public string Name { get; set; }
            public int Salary { get; set; }
        }

I also have a List:

Customer cust = new Customer() { Id=10,Name="Jack",Salary= 15000};
            Customer cust1 = new Customer() { Id = 10, Name = "Abby", Salary = 5000 };
            Customer cust2 = new Customer() { Id = 10, Name = "Zed", Salary = 152000 };

            List<Customer> CustomerList = new List<Customer>();
            list.Add(cust);
            list.Add(cust1);
            list.Add(cust2);
            CustomerList.Sort();

I understand why list.Sort wont work on Customer since Customer class has three properties and it does not know how to sort it. But if I implement the interface IComparable in Customer class I am able to sort the Customer List any way i want.

public class Customer :IComparable<Customer>
        {
            public int Id { get; set; }
            public string Name { get; set; }
            public int Salary { get; set; }

            public int CompareTo(Customer other)
            {
                return this.Salary.CompareTo(other.Salary);
            }            
        }

Now my question is.. How does implementing CompareTo method let me sort CustomerList? I am not even overriding Sort Method or anything. I am confused since I have not used CompareTo method at all.

I read https://stackoverflow.com/a/4188041/2064292 but it does not answer my question.

Answer 1

When you implement IComparable<T>, creating a public int CompareTo(T) method, what you are essentially doing is telling the sorting mechanism, which is defined elsewhere, how to sort two instances of your class by comparing one instance to another.

Like I said, the actual sorting mechanism is defined elsewhere, e.g. List<T>.Sort(). Whatever algorithm the sorting mechanism uses -- bubble sort, quick sort, etc. -- is irrelevant, but they all need to compare instances against one another over and over to produce their sorted result. Each time two instances are compared, your public int CompareTo(T) method implementation is called because that's where you define how your specific implementations are compared to one another in order to produce the sorted result.

Answer 2

While there are a lot of different sorting algorithms, they all come down to the same thing:

Move things around so that "lower" items come before "higher" items.

Therefore all sorts need to be able to understand "lower" and "higher" for the objects they are sorting.

This is easy enough with numbers; e.g. 3 < 4 is true because 3 is lower than 4. Even just with numbers though we'd have to write a different sort algorithm for int, long, decimal, double and so on, because we can't use generics here (operators like < are not available through generics) and certainly can't use < on object.

So we need to define some mechanism by which .NET can provide default "lower" and "higher" logic for all sorts of numbers, along with strings etc.

We also can't do any sorting on types we don't know about, so again we need that mechanism to know which is "lower" and which is "higher".

IComaprable<T> and IComparable do that.

We also have IComparer<T> and IComparer to allow us to define custom orders (e.g. having different logic for case-sensitive and non–case-sensitve searches) or to allow someone to provide an order on a type that doesn't implement IComparer.

Sorts generally works as:

1. If we were passed an IComparer<T> object, use it to decide which is lower or higher.

2. If we were not passed an IComparer<T> then use Comparer<T>.Default.

The use of Comparer<T>.Default means we don't need a separate sort for when we don't have an IComparer<T>, we just use the default.

Now, Comparer<T>.Default works as follows:

1. If the type implements IComparable<T> call into that.

2. Otherwise if the type implements IComparable (the old interface from before generics) then use that.

3. Otherwise throw an exception, because there's no way to know how to order anything.

Answer 3

CustomerList is a generic List with a generic type parameter Customer. The sorting algorithm implementation for the Sort() method is the one provided by the Generic List and by looking at the Microsoft documentation here you can see that actually three algorithm are used depending on the size of your list:

• If the partition size is fewer than 16 elements, it uses an insertion sort algorithm.
• If the number of partitions exceeds 2 * LogN, where N is the range of the input array, it uses a Heapsort algorithm.
• Otherwise, it uses a Quicksort algorithm.

The algorithms all rely on your implementation of IComparable for the Customer class to know how to order your customer objects.

Answer 4

Within the code for List<T>.Sort(), it will be

• casting each object to IComparable<T>,
• using that interface to call CompareTo(),
• the result from that call determines the sort order.

For example:

// Sorts a list using IComparable<T>
public static void Sort(this List<T> list)
{
   // Worst sorting algorithm ever
   for (int i = 0; i < list.Count; ++i)
   {
      for (int j = 0; j < list.Count; ++j)
      {
          // Assumes that type T implements IComparable<T>
          IComparable<T> first  = (list[i] as IComparable<T>);
          IComparable<T> second = (list[j] as IComparable<T>);

          if (first.CompareTo(second) > 0)
          {
              // wrong order
              Swap(list, i, j);
          }
      }
   }
}