Insertion Sort, Pass by Pass

Think of sorting a hand of playing cards. You hold a few cards already in order, pick up the next one, and slide it left past any card bigger than it until it lands in the right spot. Insertion sort does exactly this with an array. It treats the front of the array as a growing sorted region and, on each pass, takes the first unsorted element and shifts it leftward past every element bigger than it, stopping the moment it meets one that's smaller or equal.

Mechanically, on pass i, the element at index i is temporarily held, and the algorithm compares it to its left neighbor. If that neighbor is bigger, the neighbor shifts one spot to the right and the comparison moves one step left. This repeats until the held element meets a smaller neighbor or hits the front of the array, and that's where it settles. One pass finishes one element's journey; after n-1 passes every element has been inserted and the whole array is sorted.

The number of shifts depends entirely on how out of order the input is. A reverse-sorted array forces every new element all the way to the front, racking up 1 + 2 + ... + (n-1) shifts, the triangular number n(n-1)/2 — insertion sort's worst case. An already-sorted array needs only one comparison per element and zero shifts, since each element is already smaller than nothing to its left — its best case. This sensitivity to existing order is what sets insertion sort apart from selection sort, which does the same amount of comparing no matter how the input starts.