How many times the CompareTo method is called when a collection is sorted?

Question

If a type implements IComparable<T> and you have a collection of this type with 100 elements. When you call the Sort method on this collection, how many times would the CompareTo method be called and how? Would it be used in this manner?

CompareTo(item0, item1);
CompareTo(item1, item2);
CompareTo(item2, item3);
CompareTo(item3, item4);
...
CompareTo(item97, item98);
CompareTo(item98, item99);

EDIT: Basically what I am trying to do is to turn this way of sorting into a value-based sorting where I assign some value to each item and then sort them. It's hard to explain but I am not able to use a -1,0,1 based sorting function for this problem. But all I have is a CompareTo function that I need to use to sort the items. So I need to generate some values for each item, and then the program will sort them from the smallest value to largest.

Answer 1

Well, you can't be 100% sure (with most sorting algorithms) as it will depend on the data. For example, certain sorting algorithms will only perform N (N being the size of the collection) comparisons of the data is already sorted, but needs to be much more if it's not.

The commonly used sorting algorithms, such as MergeSort, QuickSort, and HeapSort are all O(n*log(n)), which is to say the number of comparisons will be on the order of the number of items times the log base of the number of items. (The log base will be 2 for those algorithms.) While this won't be exact, it will scale with that relationship.

If you're interested in how many times it's called for a particular sorting operation you can use something like this:

public class LoggingComparer<T> : IComparer<T>
{
    private IComparer<T> otherComparer;
    public LoggingComparer(IComparer<T> otherComparer)
    {
        this.otherComparer = otherComparer;
    }

    public int Count { get; private set; }

    public int Compare(T x, T y)
    {
        Count++;
        return otherComparer.Compare(x, y);
    }
}

It will wrap another comparer but also count the number of compare calls. Here's an example usage:

var list = new List<int>() { 5, 4, 1, 2, 3, 8, 7, 9, 0 };

LoggingComparer<int> comparer = new LoggingComparer<int>(Comparer<int>.Default);
list.Sort(comparer);
Console.WriteLine(comparer.Count);

Answer 2

Piggy backing on Servy's answer. Whatever the Asymptotic Complexity for comparison operations of the sorting algorithm is, that is how many calls will likely be made to CompareTo(). Note, this is usually a growth pattern and not an exact number of operations.