The python function below takes a value and inserts it

into an already sorted array $($A$)$:

def insert$\_$into$\_$sorted$($A$,$ value$)$:

$...$

$...$

return A

Answer the following questions:

$($a$)$ Complete the function using python $($or a different language if you prefer$).$

$($b$)$ Run your program for several different input values. Does your method

appear to work for both standard input and edge cases $($e$.$g$.$ empty arrays,

duplicate values, etc...$)?$ Why do you believe this?

$($c$)$ Describe a loop invariant that will help you prove correctness.

$($d$)$ Prove that your algorithm is correct by showing that the loop invariant

remains true during initialization, maintenance, and termination

$($e$)$ How does this relate to the correctness of the insertion sort? $($Hint: How

would you modify insertion sort to use your method?$)$

$2$