Insertion Sort

Insert each element into its correct position in the sorted portion. Fast for nearly sorted arrays.

Sorted
Key (inserting)
Shifting
Unsorted

Controls

Best: O(n) | Avg: O(n²) | Worst: O(n²) | Stable

Steps