This is the question I am looking to get answered:

These are the references below:

Q3. Let's consider a sorting problem as follow: Input: A sequence of n numbers a1,a2,,an Output: A reordering a1,a2,,an of the input sequence such that a1a2an. (1) Solve this problem by implementing InsertionSort algorhtm. Display the result for the given input A. - Implement the InsertionSort algorithm using the INSERTION-SORT pseudocode in the lecture slides. - Use the input_A generated in the "1. Generate inputs" cell. (2) In this task, we will compare the running times of your InsertionSort implementation for three different types of inputs: random, sorted in ascending order, and sorted in descending order, with the following input sizes: n=[100,1000,2000,3000,4000,5000]. That is, each type of input will have six different sizes. (Refer to the "1. Generate inputs" cell for a reference). - 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) (3) 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