Insertion Sort

Time Complexity:

• Best: O(n) - already sorted
• Average: O(n²)
• Worst: O(n²) - reverse sorted

Space Complexity: O(1)

Stable: Yes

Insertion Sort builds the final sorted array one item at a time. It picks the next element and inserts it into the correct position within the already sorted portion.

Like sorting playing cards in your hand, you pick up one card at a time and place it in the right spot among the cards you're already holding.