Mastering Algorithms with C

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

Figure 12.1. Sorting with insertion sort