# Analysis of straight insertion

I'm currently reading through N. Wirths': Algorithms + Data Structures = Programs. I'm not sure, but I think there might be an error in the analysis of the provided straight insertion sort. Screenshot of the relevant paragraph is here: screenshot

Edit: sentinel item a[0] = x, the current item that I want to insert at the appropriate place.

Sorry, another screenshot of relevant paragraph is here: screenshot2

    type index = 0..n
var a: array[0..n] of item

procedure straightinsertion
var i,j: index; x: item;
begin
for i := 2 to n do
begin x := a[i]; a[0] := x; j := i-1;
while x.key < a[j].key do
begin a[j+1] := a[j]; j := j-1;
end;
a[j+1] := x
end
end


I think, that the analysis of the number of comparisons might be wrong. He claims, that the number C_i of key comparisons in the i-th sift is at most i-1. But shouldn't it be i? Because at the worst case, since we are using sentinel, we have to make an extra comparison with the sentinel too. I claim, that:

• C_min = n-1
• C_ave = 1/4 * (n^2 + 3n - 4)
• C_max = 1/2 * (n^2 + n) -1

The number of moves M_i should then be (i-1)+2. M_min, M_ave, M_max are, I believe, correct in the text (screenshot).

Could you please confirm if I'm right or is there something I'm missing?Thank you all very much!

• What exactly is the sentinel defined as here? Also, does the author index arrays starting from 0 or starting from 1? – kotu Jun 27 at 16:40
• Sentinel is the current element that I want to sift/insert to the sorted part of an array. In this case, the arrays index start from zero. – Bomba Jun 27 at 16:42
• Perhaps I'm missing something, but why would you compare the item that you wish to insert to itself? – kotu Jun 27 at 16:52
• I've edited my question - instead of me trying to rewrite it, I'll post another screenshot. Hope this might be better, sorry for any confusion. – Bomba Jun 27 at 16:59

Edit: My apologies, misunderstood what you meant by sentinel earlier. It seems to me that you are correct, and this is indeed a typo. When you include comparison against the sentinel at $$a[0]$$, you perform $$i - 1 + 1 = i$$ comparisons on a worst case sift.

• Well, let's say I have an array [S,5,6,7,2,...] where S is sentinel at position 0 and I currently want to insert the item x=a[4] (in this case the sentinel will be set to S=7 since that was the last value that I inserted in). Now, i = 4, S = 2 and j = 3. I will compare 2 (my item I want to insert) with all the other values -> 7, 6, 5 (that's 3 comparisons) but for the while loop to terminate (since for all the previous values x<a[j], I have to make one more comparison with the sentinel S at position a[0]. So that's 4 comparisons. – Bomba Jun 27 at 17:15
• Seems like you've answered your own question! – kotu Jun 27 at 17:25
• Thank you very much. It still seems weird to me, that the author would have then the C_max correct but C_min and C_ave wrong in his text: authors' analysis – Bomba Jun 27 at 17:32