4. Consider the sorting problem as Q3. (1) Solve this problem by implementing the MergeSort algorithm. Display the result for the given input_A. - Use the MERGE-SORT pseudocode from the lecture slides to implement the MergeSort algorithm. - Use input A generated in the "1. Generate inputs" cell. (2) In this task, we will compare the running times of your MergeSort implementation for three different types of inputs: random, sorted in ascending order, and sorted in descending order, with the following input sizes: n=[1000,10000,20000,30000,40000, 50000]. This input size is ten times larger than in Q3. - First, measure the running time for all input sets. For example, there will be six running time measurements for the random set. - Then, compare the results by plotting them as a graph. (Refer to the "3. Plot" cell for a reference) * Note: You may need to regenerate the inputs after you run them in Q3, as sorting an input with a sort algorithm will result in the input becoming sorted. (4) Based on the results from (2), analyze and explain the trend of running times for the different types of inputs. - Use asymptotic notations in a Markdown cell to present your explanation. (Refer to the "4. Write equations with Markdown" cell for a reference) 5 points 1. Generate inputs 2. Measure a running time start =timer() YourAlgorithm(input_A) end = timer() print(end-start) \# time unit [seconds] 3. Plot \# As an example, Let's assume that 'elapsed_time_random' stores the running time of \# 6 different size inputs, e.g., randomLy generated input elapsed_time_random =[1,10,160,1600,10000,100000] elapsed_time_asc =[1,5,50,500,5000,50000] \# Plot elapsed_time_random plt.plot(size, elapsed_time_random, color="blue', label='Running time for random input') plt.plot(size, elapsed_time_asc, color='green", label="Running time for asc input') plt.title("Running time of algorithms") plt.xlabel("Input size") plt.ylabel("Running time[seconds]") plt.grid(True) plt.legend() plt.show() 4. Write equations with Markdown syntax - Examples: You can type (n2),(n2), and O(n2) - References http:/ftug.ctan.org/info/undergradmath/undergradmath.pdf