Insertion Sort

Various, 1959

Insertion sort, documented in computing folklore by the late 1950s, maintains a sorted prefix and grows it one item at a time. Each element is compared with its left neighbor and swapped upward until the invariant holds. The bars show index i at the boundary of the sorted region and j as the insertion probe; gold marks the active pair and teal marks the sorted prefix (and full array when complete).