Insertion Algorithm I

Problem statement

You have the sorted array of N numbers, src_arr, and an additional number x. The goal is for your code to return the sorted array, dst_arr, of N+1 numbers that include all those of arr as well as x.

Example: If src_arr=[2,5,6] and x=4, then dst_arr=[2,4,5,6]

Insertion Algorithm II: Recursive

Problem statement

You have a sorted array of N numbers, arr, and an additional number x. The goal is for your code to return a sorted array of N+1 numbers that include all those of arr as well as x. This time you want to write a recursive algorithm, i.e., a functions that calls itself for different sizes of its input array

1. Write down a few cases on paper/editor where you try to do things both ways, recursively and non-recursively.
2. Sketch the logic of your algorithm using mainly english sentences and occassional CS jargon if needed. The aim is to lay down the logic of your code
3. Write a pseudo-code based of the two previous points
4. Check your pseudo-code: Test it on the examples your wrote down in point 1. Try to see if you are tackling correctly the extremal cases (e.g. N=0,N=1, N<0, etc.