Implement recursive version of insertion sort. Remember its definition from the lectures. Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The list is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part. To sort a list of size n in ascending order: 1: Iterate from arr[1] to arr[n] over the list. 2: Compare the current element (key) to its predecessor. 3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element. Recursion idea: 1: Base Case: If list size is 1 or smaller, return. 2: Recursively sort first n-1 elements. 3: Insert last element at its correct position in sorted list.

python program