DSA — Insertion Sort

What is Insertion Sort?

Builds the sorted array one element at a time by inserting each element into its correct position.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

How it Works

[12, 11, 13, 5, 6]
 ↓
[11, 12, 13, 5, 6]
    ↓
[11, 12, 13, 5, 6]
       ↓
[5, 11, 12, 13, 6]
          ↓
[5, 6, 11, 12, 13]

Time Complexity

Case	Complexity
Best	O(n)
Average	O(n²)
Worst	O(n²)

Characteristics

• Stable sort
• In-place
• Efficient for small datasets
• Adaptive (fast on nearly sorted data)

Mini Practice

1. Implement insertion sort
2. Sort cards like a card player
3. Use for online sorting
4. Compare with other sorts

Up Next

Continue with Merge Sort — divide and conquer sorting.