This is the question I am looking to get answered:

The references are below:

Q4. 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) Import libraries In [1]: import numpy as np import sys \# Import timer lib. to measure running time from timeit import default_timer as timer \# Import plot lib. to plot results. \# You may need to install matplotlib by typing "python3 -m pip install -U matplotlib" in the terminal import matplotlib.pyplot as plt \begin{tabular}{r|l} In [2]: & Example \\ def YourAlgorithm(arg): \\ & \# write your algorithm \\ & print(arg) \end{tabular} 1. Generate inputs 1. Generate inputs In [3]: \# 1-1: Input_A (example) input_A =[23,12,56,1,23,32,3,0,10,16] \#print(input_A) \# print the input \# 1-2: Generate random input with the range of S