Quiz 6, 10/4

Suppose that the input array is "nearly sorted" in the following sense. 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 TimingSimpleSort.java 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 nearly sorted.