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[1...n] a list of integers. Output: List A'[1...n] such that A'[i] = A[i] if A'[i] is even, and A[i] = A'[j] for all I sis is n such that A[i] and A'[i] are both odd. 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[1... n) a list of integers. Output: List A'[l...n] such that A'[i] = A[i] if A'[i] is even, and A[i] = A'[j] for all I sis is n such that A[i] and A'li] 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. A pairsort(A[a], A[b]) if a b if b= a +1 if b> a+1 SOS(A[a...b])= with A' SOS(A[a... 12) || A[t2 +1...b] A' la...11 || SOS( A' [ 11 +1...b]) SOS(A" la... 121) || A" | 12 +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[1...n] a list of integers. Output: List A'[1...n] such that A'[i] = A[i] if A'[i] is even, and A[i] = A'[j] for all I sis is n such that A[i] and A'[i] are both odd. 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[1... n) a list of integers. Output: List A'[l...n] such that A'[i] = A[i] if A'[i] is even, and A[i] = A'[j] for all I sis is n such that A[i] and A'li] 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. A pairsort(A[a], A[b]) if a b if b= a +1 if b> a+1 SOS(A[a...b])= with A' SOS(A[a... 12) || A[t2 +1...b] A' la...11 || SOS( A' [ 11 +1...b]) SOS(A" la... 121) || A" | 12 +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