Insertion Sort
Insertion Sort builds the sorted array one element at a time by inserting each element into its correct position.
BeginnerTime: O(n²)Space: O(1)Stable
Take QuizCurrent Step
Press Play to start the visualization
## How Insertion Sort Works
Insertion Sort builds the sorted array one element at a time. It picks each element and inserts it into its correct position within the sorted portion.
### Algorithm Steps:
1. Consider the first element as sorted
2. Pick the next element (key)
3. Compare key with elements in the sorted portion
4. Shift larger elements right to make room
5. Insert the key in its correct position
6. Repeat for all elements
### Key Characteristics:
- **In-place**: Only requires O(1) extra space
- **Stable**: Equal elements maintain their relative order
- **Efficient for small data**: Great for nearly sorted arrays
Time & Space Complexity
| Case | Time Complexity |
|---|---|
| Best | O(n) |
| Average | O(n²) |
| Worst | O(n²) |
| Space | O(1) |
Practice Problems
10 problems81 total points
1
Basic Insertion Sort
Beginner5 pts
2
Count Shifts
Beginner5 pts
3
Insertion Position
Beginner5 pts
4
Binary Insertion Sort
Intermediate8 pts
5
Sort Nearly Sorted Array
Intermediate8 pts
6
Shell Sort
Advanced10 pts
7
Insertion Sort List
Advanced10 pts
8
Online Median
Advanced10 pts
9
Library Sort
Advanced10 pts
10
Patience Sort
Advanced10 pts