Write a program in your favorite language implementing the algorithm INSERTION SORT so that it counts the total number of comparisons for any input array, and the average number of comparisons for a set of permutations of the said array. Use as input: $($i$)$ all permutations of $<1,2,3,4>$; $($ii$)$ all permutations of $<1,2,3,4,5>$; $50$ random permutations of $<1,2,...,20>.$

For part $($i$)$ check that your result coincides with the number obtained in the lecture $(4\mathrm{.}9...)$; the input for parts $($ii$)$ and $($iii$)$ is the output you obtained in homework $1.$ Your new output should be the three averages for the cases n $=4,5,20.$