I'm curious if there's a formula/rule to find the total number of comparisons done in a sorting algorithm, particularly merge sort, selection sort, and insertion sort. I'm pretty sure with selection sort the rule is n(n-1)/2where n is the number of elements being sorted. I thought the same was the case for an insertion sort but apparently that's not true according to a practice Java test I took (with a list of 6 items the insertion sort makes 14 comparisons, according to the answer key, and 15 comparisons with a selection sort). So now I'm confused.
In general, there are no precise formulae for a couple of reasons:
There is sufficient scope for variation in implementing various sort algorithms that there can be small discrepancies between different implementations of the same algorithm.
With some algorithms, the number of comparisons depend on the elements and their initial order.
And certainly, there is no "one size fits all" formula that covers all algorithms in (say) the same complexity class.
One clue: if a sort algorithm has a best case or worst case complexity that is different from its average complexity, then the number of comparisons or the number of moves depends on the inputs.