Insertion sort

Insertion sort builds a sorted sequence one item at a time, inserting each new item into its correct position among those already processed.

In-place algorithm: An algorithm that uses only a small, fixed amount of extra memory beyond its input. Insertion sort can rearrange items within the input array using constant extra space.
Insertion sort on nearly sorted data: The use of insertion sort on sequences whose elements are already close to their final positions. Few out-of-order elements mean few shifts, bringing its running time close to linear.
Selection sort: A comparison sort that repeatedly selects the smallest remaining element and places it next in the output. Selection sort makes fewer swaps, while insertion sort is usually better on nearly sorted input.
John von Neumann: A mathematician and computer scientist whose work shaped computing, game theory, and several branches of mathematics. Von Neumann’s 1945 report described sorting procedures that included insertion-based methods.
Stable sorting algorithm: A sorting algorithm that preserves the relative order of elements with equal keys. Insertion sort is stable when it shifts only elements strictly greater than the item being inserted.
Adaptive algorithm: An algorithm whose running time improves when its input has useful structure or is partly processed. Insertion sort performs less work as the input becomes more nearly sorted.
Bubble sort: A sorting algorithm that repeatedly swaps adjacent out-of-order elements until the sequence is ordered. Both are simple quadratic sorts, but insertion sort generally performs less work in practice.
EDVAC: An early stored-program electronic computer developed in the United States after World War II. The EDVAC report helped circulate early algorithm descriptions, including insertion sorting.
Loop invariant: A property that remains true before and after each iteration of an algorithmic loop. The processed prefix is sorted at every iteration, establishing insertion sort’s correctness.
Online algorithm: An algorithm that processes input items as they arrive, without requiring the entire input in advance. Insertion sort can maintain a sorted prefix while items arrive one by one.

Linked from 5 pages