## 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).

Get Mastering Algorithms with C now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.