Interview question: Implement insertion sort algorithm in Python

In my last blog post concerning interview questions, I discussed the bubble sort algorithm, and that post can be viewed here:- https://medium.com/@tracyrenee61/interview-question-code-the-bubble-sort-algorithm-in-python-e4ff0bc16976

In this post, I intend to discuss another kind of sorting method, called the insertion sort algorithm. In the insertion sort algorithm, the unsorted element is placed at its suitable place in each iteration. In this algorithm, we assume that the first element is already sorted and then we select an unsorted element. If the unsorted element is greater than the first element it is placed to the right, otherwise it is placed to the left.

The psuedocode for the insertion sorting algorithm is:-

1. Define the function, insertion_sort, which accepts an unsorted array as input.
2. Within the function, define the variable, sorted_array, which is a copy of the unsorted array.
3. Within the function, create a for loop that will iterate from 1 through to the length of the array.
4. Within the for loop, define the variable, key, which is the ith element of sorted_array.
5. Within the for loop, define the variable, j, which is i-1.
6. Within the for loop, create a while loop that will continue as long as j is greater than or equal to 0 and the key is less than the jth element of sorted_array.