$.$ Listthefiveinversionsofthearrayh$2$;$3$;$8$;$6$;$1$i$.$

$42$ Chapter $2$ Getting Started

b$.$ What array with elements from the set f$1$; $2$; : : : ; ng has the most inversions? How many does it have?

c$.$ What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

d$.$ Give an algorithm that determines the number of inversions in any permutation on n elements in $.$n lg n$/$ worst$-$case time. $($Hint: Modify merge sort.$)$