Spotify aims to develop a recommendation system that aligns your podcast preferences with those of other users$.$ By consulting its database, Spotify seeks to identify individuals with similar tastes.

The similarity metric utilized for this recommendation system quantifies the number of reversions between podcast rankings made by users based on their preferences. Assuming the podcasts are sorted according to my rankings, the podcast in i th position of my podcast ranking is denoted as pi$.$ Your podcast ranking is represented by a series of indices a$1,$ a$2,...,$ an where ai indicates the position of podcast pi in your ranking. For instance, a$5=1$ means p$5$ is your most preferred podcast and a$2=7$ means p$2$ is the $7$th most preferred one.

$$ My podcast ranking: $1,2,...,$ n

$$ Your podcast ranking: a$1,$ a$2,....,$ an

$$ Podcasts i and j reversed if i $$ j$,$ but ai $>$ aj

$\backslash$table$[[,$PODCASTS$],[,$A$,$B$,$C$,$D$,$E$],[$My ranking,$1,2,3,4,5],[$Your ranking,$1,3,4,2,5]]$

Reversions: $(3-2),(4-2)$

Design a divide and conquer algorithm that takes such a sequence as input and returns the number of reversions in the sequence.

A$.$Design a divide & conquer algorithm for this problem. Specify how the division stage is conducted. Provide the number of sub$-$problems and their sizes. Describe the combining process. $($Note that division into two parts such that one part includes one element and the other part includes the rest is not always considered as divide & conquer. Please refrain from using such divisions.$)$

B$.$Write your algorithm in pseudocode. $($Adhere to the pseudocode conventions commonly found in textbooks.$)$

C$.$Prove that your algorithm is correct $($use induction$).$

D$.$Analyze the best case and the worst case run$-$time complexities of your algorithm. Write the corresponding recurrence relation and solve it$.$ If a running$-$time bound is provided, prove that your algorithm satisfies this bound.

E$.$Analyze the space complexity of your algorithm. Write the recurrence relation and solve it$.$