The Insertion Sort Algorithm

Insertion Sort: Basic Idea

The idea of this sort is to maintain a sorted list while taking, at each step, the next value (whatever it might be) from the remaining unsorted values, and inserting that value into its proper place in the sorted list.

Insertion Sort: Name, Input and Output

Name: SortByInsertion

Input:

• A sequence of values, all of a given type, which is called s
• Two positions in the sequence, to determine the range of values within the sequence that will be sorted, which are called firstPosition and lastPosition, and which satisfy firstPosition <= lastPosition

Output:

• The sequence of values s, sorted in ascending order between firstPosition and lastPosition, inclusive

Insertion Sort: Pseudocode

Algorithm SortByInsertion(s, firstPosition, lastPosition)
---------------------------------------------------------
while values not yet sorted
    Take next unsorted value
    Find proper place in sorted list to insert this value
    Insert the value
endwhile

Note that after each iteration the number of remaining unsorted values has been reduced by one.

Insertion Sort: Performance

We say that the insertion sort algorithm is, in general, a O(n²) algorithm, or that it has "quadratic time complexity". We will not present the arguments in detail, but they are quite similar to those used in the analysis of selection sort. In fact, many of the comparison-based sorting algorithms whose structure is essentially two nested loops turn out to be O(n²) algorithms.