Java Reference
In-Depth Information
5.
First, you consider the subarray of equally spaced integers at the indices 0, 4, and 8 (they appear in bold):
9
827
5
463
1
Now sort them to get
1
827
5
463
9
The indices 0, 4, and 8 have a separation of 4. Next, consider the integers at indices 1 and 5:
1
8
275
4
639
Sort them to get
1
4
275
8
639
Then sort the integers at indices 2 and 6; they already are in order:
14
2
758
6
39
Next, consider the integers at indices 3 and 7. Sort them to get
142
3
586
7
9
Now decrease the separation between indices to 2. You consider the integers at the indices 0, 2, 4, 6, and 8:
1
4
2
3
5
8
6
7
9
You find that they are sorted. Then consider the integers at indices 1, 3, 5, and 7:
1
4
2
3
5
8
6
7
9
Sort them to get
1
3
2
4
5
7
6
8
9
Decreasing the separation to 1 results in an ordinary insertion sort of an array that is almost sorted.
6.
9
624
8
753
8
624
9
753
8
6
249
7
53
86
2
497
5
3
862
4
975
3
862
3
975
4
8
6
2
3
9
7
5
4
2
6
5
3
8
7
9
4
2
6
5
3
8
7
9
4
2
3
5
4
8
6
9
7
Now apply a regular insertion sort.
