# Insertion sort with pairs of numbers already in order

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

$$4,5,22,23,1,2,19,20, \dots$$

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

$$\sum_{n=2}^{n/2}(2n-1)(2)$$

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

• "Average case" only makes sense if you have a probability distribution over your inputs. – David Richerby Feb 19 '16 at 1:02
• @DavidRicherby The probability distribution here is: take a random permutation $\pi(1),\ldots,\pi(n)$, and construct the array $2\pi(1),2\pi(1)+1,\ldots,2\pi(n),2\pi(n)+1$. – Yuval Filmus Feb 19 '16 at 5:19
• @YuvalFilmus "Random" means "according to a probability distribution." Which one? – David Richerby Feb 19 '16 at 6:11
• @DavidRicherby It's usually the uniform distribution under the given constraints. No need to say that explicitly. – Yuval Filmus Feb 19 '16 at 6:14
• @YuvalFilmus Oh, there is every need, seeing as the OP explicitly wants a non-uniform distribution (w.r.t. all permutations). – Raphael Feb 19 '16 at 10:00

Observe that in your class of inputs, the maximum number of inversions is not $n(n-1)$ as in the unrestricted case, but one less for each pair of elements. Since there are on average $\Theta(n^2)$ many inversions in random permutations, you'll have as many in your ordered-pairs permutations, assuming uniform randomness, because you lose at most linearly many in each.
Insertion sort is $\Theta(n^2)$ in the average case. For your kind on input, consider all elements in odd places. You can simulate an insertion sort on these elements by looking at what insertion sort is doing on the entire array. This simulation loses some constant factors, but this still shows that on average you get $\Omega(n^2)$ comparisons. Since you have a matching worst-case upper bound, you get that on average, insertion sort takes $\Theta(n^2)$ on your special arrays.