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


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

  • 4
    $\begingroup$ "Average case" only makes sense if you have a probability distribution over your inputs. $\endgroup$ – David Richerby Feb 19 '16 at 1:02
  • 1
    $\begingroup$ @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$. $\endgroup$ – Yuval Filmus Feb 19 '16 at 5:19
  • 1
    $\begingroup$ @YuvalFilmus "Random" means "according to a probability distribution." Which one? $\endgroup$ – David Richerby Feb 19 '16 at 6:11
  • 1
    $\begingroup$ @DavidRicherby It's usually the uniform distribution under the given constraints. No need to say that explicitly. $\endgroup$ – Yuval Filmus Feb 19 '16 at 6:14
  • 1
    $\begingroup$ @YuvalFilmus Oh, there is every need, seeing as the OP explicitly wants a non-uniform distribution (w.r.t. all permutations). $\endgroup$ – Raphael Feb 19 '16 at 10:00

Insertion Sort is one of the algorithms which only swaps adjacent elements if they are out of order. Therefore, it's performance is intimately tied to the number of inversions in the input; see e.g. here for a detailed explanation.

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.

For the details, find an analysis of Insertion Sort that rests on the number of inversions (e.g. in a good textbook) and change the numbers; the calculations should mostly remain the same.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.