I’m going to drop this down a notch on the assumption the OP isn’t a CS guy, but rather just a math-curious guy.

Are you actually trying to count comparisons out of math curiosity, or are you trying to develop / program a sorting algorithm? IOW are you doing physics or engineering?

The reason I ask is in the OP you talk about applying the transitive property. It’s a true fact, but it isn’t computationally free.

i.e. you said: “…because you can apply the transitive property if you know A > B and B > C, then you also know A > C and don’t need to compare those 2 directly …”

But you can only do that if you store the result of both comparisons and have a mechanism to search your stored comparisons to match them up & apply transitivity. In almost all cases doing all that involves a lot more comparisons and other costly operations than does simply comparing A to C to discover that A > C.

(**Chronos**’ mergesort example is a way to store the prior comparison results implicitly in the ordering of the sub-lists. The process of merging the sub-lists makes explicit the extra work of locating and comparing the pre-existing comparisons.)

Since you were talking about small lists, e.g. 10 to 20 members then O(f(n)) notation falls down a bit since the n isn’t big enough to bury the details.

e.g. For an ultra-naïve algorithm like bubble sort, if by luck the list is already sorted it requires n-1 list member comparisons to sort the already-sorted list. OTOH, of the list is ordered exactly backwards versus sorted order, it will take (n-1)! comparisons to sort the list. For a 10 element list that’s either 9 comparisons, or 362,880 comparisons.

And of course there are other overhead operations required: comparisons to keep track of where we are, ops to move the members around, increment and decrement counters / pointers, etc.

(What’s interesting to me is that the best, smartest, least naïve sort out there, Quicksort, has the opposite behavior to crappy, dumbest, most naïve bubble sort. Quicksort performs *worst *when the list is already sorted, whereas bubble sort performs best. As **Chronos **said just above.)