Definition
Insertion sort is like organizing cards in your hand during a card game - each element is inserted into its correct position in the already sorted portion.
Key Characteristics
- ✓Gradually expands sorted portion from the front - left side is always sorted
- ✓Very fast on nearly sorted data - best case O(n)
- ✓Stable sort - maintains order of equal elements
- ✓Efficient for small data - simple and no extra memory needed
Use Cases
Used in these scenarios:
🃏
Card Game Sorting
Organizing cards in hand as you receive them one by one during a game
📊
Real-time Data Sorting
Adding new data to a sorted list as it arrives one at a time
⚡
Nearly Sorted Data
Quickly completing the sort of already nearly sorted data
Operations
Main operations:
Find Insert Position
O(n)Find the correct position in the sorted portion for the new element.
Insert
O(1)Insert the element into its correct position in the sorted portion.
Complexity
Time Complexity
Best
O(n)
Average
O(n²)
Worst
O(n²)
Space Complexity
O(1)
Understand Deeper with Visualization
See how the algorithm works through step-by-step animations and code execution.
Start Visualization