Insertion Sort

Builds the sorted array one element at a time by lifting the current key and shifting larger elements right until the key drops into place. Excellent on small or nearly-sorted inputs.

Best

O(n)

Average

O(n²)

Worst

O(n²)

Space

O(1)

Stable

Yes