Write a Java program TimeSorts that empirically tests the three sorts Insertion sort, Selection sort, and Quick sort presented in sections 2.1 and 2.3 and present in the packages algs21 and algs23. It should have a main loop that iterates over the lengths that are powers of 2 from 2⁷ to 2¹⁷. Inside the loop, for each sort, it randomly generate an array of integers of that length, calls the sort, and, using a Stopwatch object, keeps track of the time it takes.

At the bottom of the loop it prints a formatted line containing four values:

a 6-digit integer that is the length of the array being sorted;

three double values, one for each sort, that are the elapsed times from the Stopwatch object (see below).

Here is the output from my solution. Note that your times will be different than mine but should show longer times for the first two relative to quick sort.

Length Insertion Selection Quicksort 128 0.002 0.001 0.002 256 0.001 0.001 0.001 512 0.003 0.002 0.000 1024 0.006 0.017 0.000 2048 0.004 0.018 0.002 4096 0.019 0.035 0.004 8192 0.083 0.140 0.002 16384 0.281 0.559 0.003 32768 1.269 2.235 0.006 65536 5.564 8.936 0.010 131072 23.670 35.820 0.029 link to the sort algorithm: https://algs4.cs.princeton.edu/20sorting/