Use insertion sort and the binary search from Exercise E14.13 to sort an array as described in Exercise R14.20. Implement this algorithm and measure its performance.

Data from Exercise E14.13

Consider the binary search algorithm in Section 14.6. If no match is found, the search method returns −1. Modify the method so that if a is not found, the method returns −k − 1, where k is the position before which the element should be inserted. (This is the same behavior as Arrays.binarySearch.)

Data from Exercise R14.20.

Consider the following speedup of the insertion sort algorithm of Special Topic 14.2. For each element, use the enhanced binary search algorithm that yields the insertion position for missing elements. Does this speedup have a significant impact on the efficiency of the algorithm?