Use insertion sort and the binary search from Exercise P14.8 to sort an array as described in Exercise R14.14. Implement this algorithm and measure its performance.

Complete the following file:

Use the following file:

import java.util.Scanner;

   This program tests the insertion sort algorithm by
   sorting an array that is filled with random numbers.
public class InsertionSorterTimer
   public static void main(String[] args)
      Scanner in = new Scanner(;
      System.out.print("Enter array size: ");
      int n = in.nextInt();

      // Construct random array
      int[] a = ArrayUtil.randomIntArray(n, 100);
      InsertionSorter sorter = new InsertionSorter(a);
      // Use stopwatch to time insertion sort
      StopWatch timer = new StopWatch();
      System.out.println("Elapsed time: " 
            + timer.getElapsedTime() + " milliseconds");