# History of Insertion sort

HomePage | Recent Changes | Preferences

 Revision 8 . . December 16, 2001 11:52 am by Carey Evans [rewrite with generic insertion sort, and previous article as straight insertion sort; needs checking] Revision 7 . . (edit) December 16, 2001 8:17 am by Carey Evans [once more...] Revision 6 . . (edit) December 16, 2001 8:13 am by Carey Evans [off by one, aagh] Revision 5 . . December 16, 2001 8:07 am by Carey Evans [rewrite code with useful variable names, comments, and reflecting intent of algorithm better; probably faster too] Revision 4 . . December 16, 2001 6:51 am by Carey Evans [simplify Python "pseudo-code"] Revision 3 . . (edit) December 11, 2001 5:24 pm by Hannes Hirzel [/Talk added] Revision 2 . . October 30, 2001 4:10 am by Kragen [Explained O(n) best case.]

Difference (from prior major revision) (author diff)

Changed: 1c1
 Insertion sort is a sort algorithm very similar to bubble sort; the two even compare and exchange exactly the same pairs of elements, although in a different chronological order.
 Insertion sort is a simple sort algorithm where the result is built up one entry at a time.

Changed: 3c3,11
 The algorithm is as follows:
In abstract terms, each iteration of an insertion sort removes an element from the input data, inserting it into the correct sequence in the result, until no elements are left in the input.
The choice of which element to remove from the input is arbitrary.

The implementation of the result has the greatest impact on the time taken, so an ordered tree data structure with efficient inserts and in-order traversal will give good results. Specific implementations of insertion sort using these data structures may have their own names.

## Straight insertion sort

Straight insertion sort is a very simple implementation of insertion sort.
Sorting is done in-place. The result array after n iterations is the first n entries of the input array, where the first remaining entry of the input is removed each time, and the result extends into the input when this entry is inserted:

Changed: 6c14,26
 def insertionsort(array):
 _____ result ______ ______ input ______ | < x | > x | x | ... | becomes: ` ________ result _______ ____ input ____ | < x | x | > x | ... | ` The algorithm can be written as follows:
def straightinsertionsort(array):