4. (Recall Problem 4 in Problem Set 1) Given an array A = [a1, a2, , an], a reverse is a pair (ai , aj ) such that i aj . Design a divide-and-conquer algorithm with a runtime of O(n log n) for computing the number of reverses in the array. Your solution to this question needs to include both a written explanation and an implementation of your algorithm, including: (a) Your algorithm has to be a divide and conquer algorithm that is modified from the Merge Sort algorithm. Explain how your algorithm works, including pseudocode. (b) Implement your algorithm in Python, C, C++, or Java. You MUST submit a runnable source code file. You will not receive credit if we cannot compile your code. Do NOT simply copy/paste your code into the PDF. (c) Randomly generate an array of 100 numbers and use it as input to run your code. Report on both the input to and the output of your code.

4. (Recall Problem 4 in Problem Set 1) Given an array A = [01, 02,..., an], a reverse is a pair (aj, aj) such that i aj. Design a divide-and-conquer algorithm with a runtime of O(n log n) for computing the number of reverses in the array. Your solution to this question needs to include both a written explanation and an implementation of your algorithm, including: (a) Your algorithm has to be a divide and conquer algorithm that is modified from the Merge Sort algorithm. Explain how your algorithm works, including pseudocode. (b) Implement your algorithm in Python, C, C++, or Java. You MUST submit a runnable source code file. You will not receive credit if we cannot compile your code. Do NOT simply copy/paste your code into the PDF. (c) Randomly generate an array of 100 numbers and use it as input to run your code. Report on both the input to and the output of your code