Module 101
Here is a beautiful visual step-by-step drawing of the final Gap=1 (Normal Insertion Sort) phase of Shell Sort using your exact array.
FINAL PASS → GAP = 1 (INSERTION SORT ON ENTIRE ARRAY)
Starting Array (after Gap=2):
Index: 0 1 2 3 4 5 6 7 8 9
Value: 9 12 34 23 41 45 67 56 89 78
↑ ↑ ↑ ↑ ↑
Sorted Zone Current Rest
Now we insert one by one from index 3 to 9.
Step-by-Step Visual (Like Animation)
| Step | Element to Insert | Action | Array After Insertion |
|---|---|---|---|
| 1 | 23 (index 3) | Shift 34 → right, insert 23 | 9 12 23 34 41 45 67 56 89 78 |
| 2 | 41 (index 4) | Already in correct position | No change |
| 3 | 45 (index 5) | Already correct | No change |
| 4 | 67 (index 6) | Already correct | No change |
| 5 | 56 (index 7) | Shift 67 → right, insert 56 | 9 12 23 34 41 45 56 67 89 78 |
| 6 | 89 (index 8) | Already correct | No change |
| 7 | 78 (index 9) | Shift 89 → right, insert 78 | 9 12 23 34 41 45 56 67 78 89 |
FULL GRAPHICAL ANIMATION (Text Drawing)
Initial (after gap=2):
[ 9 ] [12] [34] [23] [41] [45] [67] [56] [89] [78]
↑ ←←← insert 23 here
↓
[ 9 ] [12] [23] [34] [41] [45] [67] [56] [89] [78]
Next 41, 45, 67 → already in place
[ 9 ] [12] [23] [34] [41] [45] [67] [56] [89] [78]
Now insert 56:
[ 9 ] [12] [23] [34] [41] [45] [67] [56] [89] [78]
↑←← shift 67
[ 9 ] [12] [23] [34] [41] [45] [56] [67] [89] [78]
Now insert 78:
[ 9 ] [12] [23] [34] [41] [45] [56] [67] [89] [78]
↑←← shift 89
[ 9 ] [12] [23] [34] [41] [45] [56] [67] [78] [89]
FINAL SORTED ARRAY
Bar Graph Style (Vertical – Easy to Draw in Exam)
90 │ 89
80 │ 78
70 │ 67
60 │ 56
50 │ 45
40 │ 41
30 │ 34 23
20 │ 12
10 │ 9
└─────────────────────────────────────────────
0 1 2 3 4 5 6 7 8 9 → Index
After final insertion sort → perfectly increasing bars!
Key Observations (Write This in Exam!)
- Only 3 elements needed shifting in final pass: 23, 56, 78
- Pure Insertion Sort on original array would shift many more times
- Shell Sort pre-sorts with larger gaps → fewer shifts in final pass → much faster
You can now draw this on paper exactly like this in your exam or viva and get full marks!
Want me to make a colored image or PDF of this? Just say!