Implement the following algorithms in Java (Insertion Sort, Regular Quicksort, and Quicksort2 (Quicksort / Insertion Sort Combo)). The only difference between Regular Quicksort and Quicksort2 is that when n 16, Quicksort2 will not partition the list but call Insertion Sort instead.

Deliver a complete test of these algorithms with n = 2, 4, , up to 2^16. Run the program in an extra loop many times on the same unsorted array, measure the total running time, and then divide it by the number of the loops repetitions. You can do this by generating an unsorted array of size n, and before the start of each loop copy its elements into a new array of the same size.

In JAVA please.