Your program must be in JAVA. Submit a soft copy of your program and the produced output. Also include a short discussion of the results, tabulating the results, and comparing them with the theoretical values.

This is a simple programming assignment to implement insertion sort algorithm and to observe its worst- case, best-case, and average-case performance. The performance measurement is in terms of the number of key-comparisons, rather than the actual running time. Implement insertion-sort algorithm without use of recursion. (A recursive implementation of insertion sort for large size n may cause run-time stack overflow.) To keep track of the number of key-comparisons, it is recommended that the sorting algorithm makes use of a Boolean function SMALLER(A, i,j) to do the following: . Increment a global counter, COMPCOUNT, to keep track of the number of key-comparisons per formed by the algorithm. (This count is initialized to 0 at the beginning of the algorithm.) Perform a comparison between Ali] and AReturn TRUE if A[i]