0.3.5 Insertion Sort
The Insertion Sort is slow when compared to the n log2 n algorithms
like Quicksort, Mergesort and Heapsort. It has one redeeming
characteristic, however: it is very fast for ``almost sorted'' data.
For this reason several other algorithms have been designed to nearly
sort a data set and then call the Insertion Sort as their last step.
The most notable of these is the algorithm designed by D.L. Shell
called the Shellsort.
The insertion sort operates by finding the proper location of an item
in an already sorted subset of data and then shifting the range of
data via a ripple-shift operation in such a way as to leave a hole for
the item to be inserted. The subset of already sorted data is
initially empty and grows by one element with each ripple-shift,
insert operation.
| 
Search