Implement a recursive version of insertion sort. Remember its definition from the lectures.

Insertion sort is a simple sorting algorithm that works similarly 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 in 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.