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 &lt; 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!
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.