1 Recursive sorts are easier to write in functional style than others. Two recursive sorts are Quicksort and Mergesort. Write functional versions of (a) Quicksort; (b) Mergesort in an imperative language of your choice (e.g., C, Ada, C-H-, Python), using an array of integers as your basic data structure.
2 It is possible to write nonrecursive programs that implement recursive algorithms using a stack, but at the cost of extra source code complexity (a necessary overhead of using a nonrecursive language like FORTRAN).
Write nonrecursive versions of (a) Quicksort; (b) Mergesort. Show the difficulties of the added complexity. (c) Which of the two sorts is easier to implement nonrecursively? Why?
3 Which of the following functions are referentially transparent? Explain your reasoning.