n a sequence S $=[$S$,$ S$2,...,$ Sn$]$ of n integers, an inversion is a pair of elements s$,$ and s$,$ where

i s$.$ For example, in the sequence

S $=2,1,5,3,4$

the pairs $(2,1),(5,3)$ and $(5,4)$ are inversions.

An array with n elements may have as many as

n$($n $1)$

$2$

n$($n$-1)$

the best

inversions. When the number of inversions, k$,$ may be any value between $0$ and $2$

algorithm for counting inversions has running time $0($n log n$).$ There also exists a O$($n $+$ k$)$

algorithm for counting inversions, which is $0($n$^2)$ when k $0(^2).$

Your goal in this lab is to create two algorithms which count the number of inversions in an input

sequence:

Input: An array A of n integers in the

range

$1$ to n$.$

Output: An integer, corresponding to the number of inversions in A$.$

The first algorithm will have a $0($n log n$)$ runtime and will be better for counting inversions

when k$>$ n$.$ The second algorithm will have runtime $0($n $+$ k$)$ and will be better when kn

$($i$.$e$.0($n $+$ n$)=0($n$)).$

Bonus:

Time permitting, you should try to implement them.