Part $1$: Implement Insertion Sort

Recall from lecture the pseudocode for the Insertion Sort algorithm:

insertionSort $($A$)$ :

for each index i in length $(A)$ :

let jlarri

while $j>0$ and $A[j-1]>A[j]$ :

swap $A[j]$ and $A[j-1]$

jlarrj$-1$

In the

sortingFunctions.py file, implement the insertionsort $()$ function.

a$)$ Recall that insertionSort $()$ is an in$-$place algorithm, meaning it modifies

the original data input directly and does not require additional space.

While you may create additional variables $($e$.$g$.,$ i$,$ j$),$ your implementation of

insertionSort $()$ should not create or return a new list.

Test your code.

a$)$ You can run the test code by running the following command in the command

line from your Lab$3$ folder: