What is Insertion Sort?

Insertion Sort builds a sorted array one element at a time. It’s like sorting playing cards in your hand - you pick up each card and insert it into the correct position among the cards you’re already holding.

The Basic Idea

Here’s how insertion sort works:

How It Works

1. Start with first element: Consider it sorted
2. Pick next element: Take the next unsorted element
3. Compare and shift: Compare with sorted elements, shift larger ones right
4. Insert: Place element in correct position
5. Repeat: Continue until all elements are sorted

Visual Example

Watch insertion sort in action:

Key Characteristics

• Time complexity: O(n²) worst/average, O(n) best (nearly sorted)
• Space complexity: O(1) - in-place sorting
• Stable: Yes - maintains relative order of equal elements
• Adaptive: Efficient for nearly sorted arrays

Real-World Analogy

Think of sorting cards in your hand. You pick up one card at a time and insert it into the correct position among the cards you’re already holding sorted.

When to Use

Insertion sort is good for:

• Small datasets
• Nearly sorted arrays
• Educational purposes
• When stability matters
• Simple implementations

What’s Next?

Now that you know what insertion sort is, let’s see exactly how it works step-by-step.