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:

The first sequence in the series, is the empty sequence. I.e., .
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.