To receive full credit for this lab, you need to use the cons operator, multiple function bodies, and let expressions. Each of the two problems will:

Have $2$ function bodies

Use let$-$in$-$end in one function body

Be recursive $($in the let$-$in$-$end function body$)$

Note that you will use the function that you write in the first problem to solve the second problem.

Write a function named split that takes as an argument a two$-$tuple that consists of a list and a pivot value$),$ and returns a two$-$tuple that contains two lists. The first list is composed of all the elements in the original list that are strictly less than the pivot value. The second list returned is composed of all the elements that are greater than or equal to the pivot value. The type of this function is $fn$: int list $*$ int $->$ int list $*$ int list

Hints:

What is the base case?

$O$ an empty list

What is the recursive case?

If you remove the first element, and recursively split the remaining elements according to the pivot, you can then use an if statement to place that removed item into the correct list.

Write a function named quicksort that takes a list as an argument. This function uses the quicksort algorithm to sort the list, and returns the sorted list. This function is of the following type: fn : int list $->$ int list.

a$.$ Remember that the quicksort algorithm works as follows:

i$.$ First, a pivot is chosen. For this problem, always choose the first element in the list as the pivot.

ii$.$ Then, the list $($without the pivot$)$ is split into two halves $($as described in problem $1,$ so you can use that function here!$)$ iii. Then, those two haves are each recursively sorted, and recombined into a list, with the pivot in the middle. $($Hint: you can use the @ concatenation operator here.$)$