## Implementation and Analysis of Insertion Sort

Insertion sort works fundamentally by inserting elements
from an unsorted set one at a time into a sorted set. In the
implementation presented here, both of these sets reside in
`data`

, a single block of contiguous storage.
Initially, `data`

contains the unsorted set
consisting of `size`

elements. As
*issort* runs, `data`

gradually becomes consumed by the sorted set until when
*issort* returns, `data`

is completely sorted. Although this implementation uses contiguous
storage, insertion sort can easily be adapted to work with linked
lists efficiently, something not all sorts can claim.

Insertion sort revolves around a single nested loop (see Example 12.1). The outer loop,
`j`

, controls which element from the unsorted
set is currently being inserted among the sorted elements. Since the
element just to the right of the sorted set is always the next to be
inserted, we can also think of `j`

as the
position dividing the sorted and unsorted sets in
`data`

. For each element at position
`j`

, an inner loop,
`i`

, is used to cycle backward through the
set of sorted elements until the proper position for the element is
found. As we move backward through the set, each element at position
`i`

is copied one position to the right to
make room for the insertion. Once `j`

reaches
the end of the unsorted set, `data`

is sorted
(see Figure 12.1).