Let A[l..n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.

a) Show the insertion sort algorithm. Explain clearly how it works.

b) Modify the insertion sort algorithm to count the number of inversions in the input array.

c) Trace your algorithm for question b above as it counts the number of inversions in this array: [40, 30, 20, 10].

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

a) In pseudo-code, the Insertion Sort algorithm can be represented like below (two nested loops):

swaps=0

for j = 1 to array.size do

{aux= array[j] //temporary variable used for swapping the compared items

//the item array[j] is inserted into sorted sub-array array[1 . . j − 1]

i = j − 1

While (i > 0) and (array[i] > aux) do

{array[i +1] = array[i]...

This is only a preview of the solution. Please use the purchase button to see the entire solution