Insertion Sort — visual-cs

🃏 How Insertion Sort Works

Imagine you're sorting a hand of playing cards. You pick up one card at a time and slide it left past all larger cards until it finds its correct position in the sorted portion.

Algorithm Steps

Start with the second element (first element is trivially sorted)
Pick up the current element as the key
Compare the key with elements to its left
Shift larger elements one position to the right
Insert the key into the gap created
Repeat for all remaining elements

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]
    j = j - 1
  arr[j+1] = key

Time & Space Complexity

Case	Time	When
Best	O(n)	Array already sorted
Average	O(n²)	Random order
Worst	O(n²)	Reverse sorted
Space	O(1)	In-place sorting

Key Properties

Stable: Equal elements maintain their relative order
In-place: Only requires O(1) extra memory
Adaptive: Efficient for nearly sorted data
Online: Can sort a list as it receives elements

When to Use

Insertion sort excels when the data is nearly sorted or the array is small. It's often used as the base case for hybrid algorithms like Timsort (used in Python and Java) when subarrays become small enough that the overhead of more complex algorithms isn't worth it.