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

$<($that is$,$ appears before $$ in the sequence$)$ and $>.$ For example, in the sequence

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

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

An array with $$ elements may have as many as

$($

$2)=(1)$

$2$

inversions. When the number of inversions, $,$ may be any value between $0$ and $(1)$

$2,$ the best

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

algorithm for counting inversions, which is $(2)$ when $$ in $(2).$

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

sequence:

Input: An array $$ of $$ integers in the range $1$ to $.$

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

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

when $>.$ The second algorithm will have runtime $(+)$ and will be better when $<=$

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

Bonus:

Time permitting, you should try to implement them.