Insertion Sort builds the sorted array one element at a time. For each element, it finds the correct
position among the already-sorted elements and inserts it there by shifting elements to make room.
Step: 0 / 0
Click "Start" to begin the visualization
Current Key
Comparing
Sorted
Speed:500ms
INSERTION-SORT(A):
for i = 2 to n:
key = A[i]
j = i - 1
while j > 0 and A[j] > key:
A[j+1] = A[j]
j = j - 1
A[j+1] = key
Complexity Analysis
Time Complexity:
Best Case: O(n) ā Array is already sorted
Average Case: O(nĀ²)
Worst Case: O(nĀ²) ā Array is reverse sorted
Space Complexity: O(1) ā In-place sorting
Stable: Yes ā Equal elements maintain their relative order