How does in-place insertion-sort work without a second data structure?

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.