I am currently attempting to work out the number of comparisons that is done by insertion sort when the elements are already in sorted pairs, for example
Currently working to solve for the worst and average case number of comparisons done when a sentinel is used.
For worst case where each pair is out of order, what I've worked out is that the pattern for comparison goes $1 + 3 + 3 + 5 + 5 ... + n + n$, leading to a summation
and I solved it to $(n^2+4/2) - 3 - (n-2)$.
Does this look about right? I'm now having trouble attempting to solve for the average case. Any idea how to go about this? Thanks for any help