I'm going through CLRS 3e and executing exercises to obtain a better understanding of CS fundamentals.
Below is my solution to the following exercise from chapter 2:
We can express insertion sort as a recursive procedure as follows. In order to sort \$A[*1..n*]\$, we recursively sort \$A[*1..n-1*]\$ and then insert \$A[*n*]\$ into the sorted array \$A[*1..n-1*]\$. Write a recurrence for the running time of this recursive version of insertion sort.
I was able to come up with a recurrence of:
T(N) = O(1) if N <= 1; T(N-1) + O(N) if N > 1
NOTE: The \$O\$ is supposed to represent theta notation.
import random def recursive_insertion_sort(A, n): if n < 1: return A recursive_insertion_sort(A, n - 1) key = A[n] while n > 0 and key < A[n - 1]: A[n] = A[n - 1] n -= 1 A[n] = key return A A = [3, 1, 0, 2, 3] B = random.sample(range(1, 11), 10) C = random.sample(range(1, 11), 10) D = random.sample(range(1, 11), 10) E =  F =  assert recursive_insertion_sort(A, len(A) - 1) == sorted(A) assert recursive_insertion_sort(B, len(B) - 1) == sorted(B) assert recursive_insertion_sort(C, len(C) - 1) == sorted(C) assert recursive_insertion_sort(D, len(D) - 1) == sorted(D) assert recursive_insertion_sort(E, len(E) - 1) == sorted(E) assert recursive_insertion_sort(F, len(F) - 1) == sorted(F)
I struggle with translating recursive algorithms to code. By my understanding this code is a correct recursive insertion sort due to the invariant that the array at \$A[0.. n - 1]\$ is a sorted array of the first \$n - 1\$ elements of the entire array \$A[0...n]\$.
I do not have a formal CS background so I'm unsure if this invariant holds up to more rigorous analysis. Furthermore if anyone has suggestions to how I can make this code cleaner that would be appreciated. As an aside I am trying to right this code w/o the use of built in functions aside from very primitive (ex.