$1.$ Implement the Insertion Sort algorithm as discussed in Lecture $1.$

$($Hint: use the function checked$\_$sorted to check if your output is

indeed sorted.$)$

$2.$ Implement the Merge Sort algorithm as discussed in Lecture $2.$

$($Hint: use the function checked sorted to check if your output is

indeed sorted.$)$

$3.$ Implement the Heap Sort algorithm as discussed in Lecture $2.$

$($Hint: use the function checked sorted to check if your output is

indeed sorted.$)$

$4.$ For each algorithm, try different ranges of numbers to be sorted

to 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.