Correct answer will be upvoted!

Consider the problem of sorting the odd elements in a list of integers while keeping the even ones unchanged in their original places. Sort the odd elements in a list (ODDSORT) Input: A[l... nj a list of integers. Output: List A' [l... nj such that A' [1] = A[/] if A' [I] is even, and A' [I] = A'[]l for all 1sis js n such that A' [I] and A' []I are both odd. (1 point) Below is another self-reduction for the ODDSORT problem. State a recursive algo- rithm using pseudocode for solving the ODDSORT problem based on this self-reduction. if a b if b= a +1 if b> a+1 SOS(A[a...b]) = with A A" pairsort(A[al, A[b) A SOS(Ala... t21 || A[t2 +1...b] A'la...] SOS(A' [ 11 +1...b) SOSA" a... (2) || A"t2 +1...b] (2+2 points) Using the same reduction as in the previous question, state a recurrence T'(n) that expresses the worst case running time of the recursive algorithm. From this recurrence, find a tight (Big-Theta) expression for T'(n). Hint: the Master Theorem may be the easiest solution here. Consider the problem of sorting the odd elements in a list of integers while keeping the even ones unchanged in their original places. Sort the odd elements in a list (ODDSORT) Input: A[l... nj a list of integers. Output: List A' [l... nj such that A' [1] = A[/] if A' [I] is even, and A' [I] = A'[]l for all 1sis js n such that A' [I] and A' []I are both odd. (1 point) Below is another self-reduction for the ODDSORT problem. State a recursive algo- rithm using pseudocode for solving the ODDSORT problem based on this self-reduction. if a b if b= a +1 if b> a+1 SOS(A[a...b]) = with A A" pairsort(A[al, A[b) A SOS(Ala... t21 || A[t2 +1...b] A'la...] SOS(A' [ 11 +1...b) SOSA" a... (2) || A"t2 +1...b] (2+2 points) Using the same reduction as in the previous question, state a recurrence T'(n) that expresses the worst case running time of the recursive algorithm. From this recurrence, find a tight (Big-Theta) expression for T'(n). Hint: the Master Theorem may be the easiest solution here