Growing an ordered prefix
The algorithm maintains a sorted prefix beginning with one item. For each next item, it saves the value and moves larger prefix elements rightward until there is a place for it. Repeating the insertion eventually includes the whole sequence.
The invariant is that processed items are already ordered. Making room does not disturb their relative order. After the saved item is placed, the enlarged prefix is sorted, connecting the local insertion step to correctness of the complete procedure.
References: [1]
Inversions measure the required movement
An inversion is a pair appearing in the opposite order from the target. In an adjacent-exchange implementation, each exchange removes one inversion, so the exchange count equals the initial inversion count. Comparisons also include checks that stop the insertion.
Distinct keys in reverse order have quadratically many inversions, producing O(n²) worst-case time. An already sorted sequence needs only linear checking in the usual implementation. Adaptation to existing order is an input-sensitive property, not a guarantee shared by every sorting method.
Stability and useful workloads
Moving only strictly larger keys preserves the input order of equal-key records, making the usual algorithm stable. An array implementation needs only a few temporary values rather than another full-sized array.
These benefits do not remove quadratic work on large disordered inputs. Hybrid algorithms can use insertion sort for small subarrays to reduce overhead, with thresholds depending on implementation and environment. Nonconstant key comparisons, such as long-string comparisons, also require a separate cost allowance.