$1.$ Implement the Insertion Sort algorithm.$($Hint: use the function checked$\_$sorted to check if your output isindeed sorted.$)$

$2.$ Implement the Merge Sort algorithm.$($Hint: use the function checked sorted to check if your output isindeed sorted.$)$

$3.$ Implement the Heap Sort algorithm.$($Hint: use the function checked sorted to check if your output isindeed sorted.$)$

$4.$ For each algorithm, try different ranges of numbers to be sortedto test the performance and time complexity.

For example:a$.$ Array$[1\mathrm{.}100]$b$.$ Array$[1\mathrm{.}1000]$c$.$ array$[1\mathrm{.}10000]$d$.$ Array$[1\mathrm{.}100000]$e$.$ Array$[1\mathrm{.}1000000]$f$.$

Write a paragraph discussing your findings on how the different sizes affected the time complexity. Discuss which algorithm outperformed the other and why.

g$.$ Graphs are encouraged for visualization and to draw conclusions, but not required.