next up previous contents index Search
Next: Analysis Up: 0.3 Sorting Algorithms Previous: 0.3.4 Benchmarking the Quicksort

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.

Scott Gasch