Data Structures and Algorithms with Object-Oriented Design Patterns in C++

# Insertion Sorting

The first class of sorting algorithm that we consider comprises algorithms that sort by insertion  . An algorithm that sorts by insertion takes the initial, unsorted sequence, , and computes a series of sorted sequences , as follows:

1. The first sequence in the series, is the empty sequence. I.e., .
2. Given a sequence in the series, for , the next sequence in the series, , is obtained by inserting the element of the unsorted sequence into the correct position in .
Each sequence , , contains the first i elements of the unsorted sequence S. Therefore, the final sequence in the series, , is the sorted sequence we seek. I.e., .

Figure  illustrates the insertion sorting algorithm. The figure shows the progression of the insertion sorting algorithm as it sorts an array of ten integers. The array is sorted in place  . I.e., the initial unsorted sequence, S, and the series of sorted sequences, , occupy the same array.

Figure: Insertion Sorting

In the step, the element at position i in the array is inserted into the sorted sequence which occupies array positions 0 to (i-1). After this is done, array positions 0 to i contain the i+1 elements of . Array positions (i+1) to (n-1) contain the remaining n-i-1 elements of the unsorted sequence S.

As shown in Figure , the first step (i=0) is trivial--inserting an element into the empty list involves no work. Altogether, n-1 non-trivial insertions are required to sort a list of n elements.