What is Insertion Sort?

Insertion Sort works the way you sort playing cards in your hand.

Idea:

• Assume the left part is sorted
• Take one element from the right
• Insert it into its correct position in the sorted part

Step-by-Step Example

Given array:

[64, 25, 12, 22, 11]

Pass 1 (i = 1, key = 25)

Sorted part: [64]

• 25 < 64 → shift 64 right

[25, 64, 12, 22, 11]

Pass 2 (i = 2, key = 12)

Sorted part: [25, 64]

• 12 < 64 → shift