Like sorting playing cards in your hand, hold one value as key, shift larger values to the right, and insert key into the resulting hole.

A bar-chart simulator of insertion sort

Play, step, or seek with the slider. The pink floating bar in the lower row is the held key.

Best caseO(n)

AverageO(n²)

Worst caseO(n²)

Extra spaceO(1)

StableYes

StrengthNearly sorted input

Efficient on nearly sorted arrays

Only values larger than key are shifted, so nearly sorted input needs little movement and approaches O(n) time. Compare Nearly sorted with Reversed. Insertion sort is also efficient on small ranges and is used within many production sorting implementations.

Equal values are not shifted past the key, preserving their original order.

Coding exercises

The shift count also equals the inversion count. If values arrive one at a time, use bisect.insort to find an insertion position, but inserting into a Python list still takes O(n), giving O(n²) overall. For larger workloads, consider a different data structure such as Heap.