Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
The key step of any insertion sorting algorithm involves the insertion of an item into a sorted sequence. There are two aspects to an insertion--finding the correct position in the sequence at which to insert the new element and moving all the elements over to make room for the new one.
This section presents the straight insertion sorting algorithm. Straight insertion sorting uses a linear search to locate the position at which the next element is to be inserted.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.