def insertion_sort(a): n = len(a) i = 1 while i < n: x = a[i] j = i - 1 while j >= 0 and a[j] > x: a[j + 1] = a[j] j = j - 1 a[j + 1] = x i = i + 1

One way to recognize that this is an imperative function is that it does not even return anything. We call it only for its side effect of moving the elements in a around so they are arranged in sorted order.

Question 1: Towards Functional Programming

In this question, you are asked to implement Insertion Sort as a pure function. To qualify as a pure function, your insertion_sort function has to satisfy the following conditions:

It does not modify the input array a as the above implementation does. Instead, it should return a new array containing the sorted elements.

It may create and initialize variables but not modify them. In the above insertion_sort implementation, the assignments n = len(a), i = 1, x = a[i + 1], and j = i are all fine because they create new variables and specify their values. The assignments j = j + 1, a[j + 1] = a[j], a[j + 1] = x, and i = i + 1 are not because they overwrite i, j or an element of the array a. If you are tempted to write a for-loop

for x in a: ...

this is also inherently imperative because it assigns a new value to x in each iteration. So loops are simply not possible.

You should implement insertion_sort as a recursive function. It is okay (and necessary) to implement a helper function that insertion_sort can use to implement the process of inserting x in the right position among the already sorted elements. This helper function needs to satisfy the same conditions: no modification of the function arguments or local variables.