The array is split into a sorted left part and an unsorted right part; each round takes the first unsorted element, shifts the larger sorted elements one slot right, and drops it into the gap.

* The boundary walks right; each round lifts out cur, shifts the larger cells, and drops cur into the gap. *

The trick is that you do not need a separate sorted sequence — the left end of the same array can play that role, and the boundary between the two parts walks rightwards until it reaches the end.

Each round:

1. Take the next element from the unsorted (right) side and save it in a variable, cur. Saving it is essential: its slot is about to be overwritten.
2. Walk leftwards through the sorted part. As long as an element is larger than cur, move it one position to the right. Each move opens the gap one slot further left.
3. When you meet an element that is not larger than cur (or you fall off the left end), the gap is at cur's correct position — write it there.

for (int k = 1; k < n; k++) {
  int cur = data[k];                  // save it, its slot gets overwritten
  int j = k;
  while (j > 0 && data[j-1] > cur) {  // walk left while elements are bigger
    data[j] = data[j-1];              // shift right
    j--;
  }
  data[j] = cur;                      // drop into the gap
}

Why the loop starts at $k=1$: a one-element region is trivially sorted, so the first element counts as the initial sorted part and needs no work.

Why shifting, not swapping: a swap is three assignments, a shift is one. Since cur is held safely in a variable, each displaced element only needs to be copied one slot right, and cur is written exactly once at the end.

Tip: the cost is the number of moves, and the moves are exactly the number of inversions — which is why insertion-sort degenerates to $O(n^2)$ on reversed input but is nearly $O(n)$ on almost-sorted input. That best-case behaviour is why it is the standard choice for small or nearly-sorted arrays.

Go deeper:

• VisuAlgo — sorting visualiser — step the shifting one operation at a time, on your own input.

Worst case $8n-2$: two for the initial assignment, $1 + 2n$ for the loop control, three two-operation statements for each of the $n-1$ iterations, and one for the return.

Algorithm arrayMax(A, n)                    # operations
  currentMax ← A[0]                              2
  for i ← 1 to n − 1 do                       1 + 2n
    if A[i] > currentMax then                2(n − 1)
      currentMax ← A[i]                      2(n − 1)
    { increment counter i }                  2(n − 1)
  return currentMax                              1
                            Total (worst case):  8n − 2

Reading the tricky lines:

• currentMax ← A[0] costs 2: one index into the array, one assignment.
• The for header costs 1 + 2n: one initialisation, then for each of the $n$ tests a comparison and its evaluation. Note the loop test runs once more than the body — the final test is the one that fails.
• Each of the three body lines costs 2 and runs $n-1$ times, hence $3 \cdot 2(n-1)$.
• return costs 1.

Summing: $2 + (1 + 2n) + 6(n-1) + 1 = 8n - 2$.

The individual numbers matter far less than the shape: whatever you decide an array index "really" costs, the total stays of the form $an + b$ — linear. That is the result that survives, and it is the only one the O-notation will keep.