Quiz 6, 10/4
Suppose that the input array is "nearly sorted" in the following
Imagine the array as being partitioned into blocks of 5 consecutive
elements, with block 1 being the first 5 elements (i.e., in slots 0 through 4),
block 2 being the next 5 elements (i.e., in slots 5 through 9), and so on.
The last block may have fewer than 5 elements.
Now suppose that all elements in block 1 are smaller than all elements in block 2 which are all
smaller than elements in block 3, and so on.
However, within each block the elements may be in arbitrary order.
Modify the insertionSort method in
so that it takes advantage of the fact that the array given to
it is nearly sorted in the sense described above.
The modified insertionSort method is expected to be much
more efficient than the original insertionSort method
since the modified method starts with an array that is