In this question, you are asked to implement Insertion Sort as a pure function. Since I haven't introduced you to Haskell sufficiently yet, you should use Python or Java to implement your insertion_sort function. Python and Java are imperative languages that allow side effects. However, nobody forces us to use this ability. We can effectively program in a functional style in both Python and Java by never updating variables (and thus without using loops). 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