Insertion Sort Example
Sorting Algorithms
Click on the visualization and hit the SPACE BAR to progress to the next step. Hit the R key to reset it.
Insertion Sort Example:
Initial Array: [6, 8, 3, 2, 7, 5, 1, 4]
First Iteration: [6][ 8, 3, 2, 7, 5, 1, 4]
Step-by-Step Process:
Start with the second element (index 1) and compare it with the previous elements, inserting it into the correct position.
Iteration 1 (Index 1: 8):
Current element: 8
Compare 8 with 6 (previous element). Since 8 > 6, it stays in its place.
Array after iteration 1: [6, 8][ 3, 2, 7, 5, 1, 4]
Iteration 2 (Index 2: 3):
Current element: 3
Compare 3 with 8: 3 < 8 → shift 8 to the right.
Compare 3 with 6: 3 < 6 → shift 6 to the right.
Insert 3 at index 0.
Array after iteration 2: [3, 6, 8][ 2, 7, 5, 1, 4]
Iteration 3 (Index 3: 2):
Current element: 2
Compare 2 with 8: 2 < 8 → shift 8 to the right.
Compare 2 with 6: 2 < 6 → shift 6 to the right.
Compare 2 with 3: 2 < 3 → shift 3 to the right.
Insert 2 at index 0.
Array after iteration 3: [2, 3, 6, 8][ 7, 5, 1, 4]
Iteration 4 (Index 4: 7):
Current element: 7
Compare 7 with 8: 7 < 8 → shift 8 to the right.
Compare 7 with 6: 7 > 6 → stop shifting.
Insert 7 at index 3.
Array after iteration 4: [2, 3, 6, 7, 8][ 5, 1, 4]
Iteration 5 (Index 5: 5):
Current element: 5
Compare 5 with 8: 5 < 8 → shift 8 to the right.
Compare 5 with 7: 5 < 7 → shift 7 to the right.
Compare 5 with 6: 5 < 6 → shift 6 to the right.
Compare 5 with 3: 5 > 3 → stop shifting.
Insert 5 at index 2.
Array after iteration 5: [2, 3, 5, 6, 7, 8][ 1, 4]
Iteration 6 (Index 6: 1):
Current element: 1
Compare 1 with 8: 1 < 8 → shift 8 to the right.
Compare 1 with 7: 1 < 7 → shift 7 to the right.
Compare 1 with 6: 1 < 6 → shift 6 to the right.
Compare 1 with 5: 1 < 5 → shift 5 to the right.
Compare 1 with 3: 1 < 3 → shift 3 to the right.
Compare 1 with 2: 1 < 2 → shift 2 to the right.
Insert 1 at index 0.
Array after iteration 6: [1, 2, 3, 5, 6, 7, 8][ 4]
Iteration 7 (Index 7: 4):
Current element: 4
Compare 4 with 8: 4 < 8 → shift 8 to the right.
Compare 4 with 7: 4 < 7 → shift 7 to the right.
Compare 4 with 6: 4 < 6 → shift 6 to the right.
Compare 4 with 5: 4 < 5 → shift 5 to the right.
Compare 4 with 3: 4 > 3 → stop shifting.
Insert 4 at index 3.
Array after iteration 7: [1, 2, 3, 4, 5, 6, 7, 8]
Final Sorted Array:
[1, 2, 3, 4, 5, 6, 7, 8]
Summary of Key Points:
Insertion sort works by iterating through the array, picking one element at a time, and shifting larger elements to the right to make space for the current element to be inserted in its correct position.
The algorithm sorts the array incrementally, ensuring that the left portion of the array is sorted at each step.
Insertion Sort Slide Deck - This pdf presentation has more examples to practice with.