Insertion Sort

O(n²)

Colour Guide

KEY (Being Inserted)

Shifting to Make Room

Sorted Portion

Comparisons: 0 Shifts: 0

Speed

💡 Think of sorting a hand of cards: pick each new card and slide it left into its correct position among the already-sorted cards.

Input

Pseudocode

for i = 1 to n-1: key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j+1] = arr[j] (shift right) j = j - 1 arr[j+1] = key (insert)

Step Log

Complexity

Best Case	O(n)
Worst Case	O(n²)
Space	O(1)