Sorting lists

You will implement the sorting algorithm Quicksort. The algorithm works in two steps. First it splits the list which is to be sorted into two lists and sorts these two lists recursively. In the second step it puts the results back together. The difference to mergesort lies in the way the list is split and is put back together. In part a you will implement an easy version of the algorithm. For extra credit you can solve part b which does the splitting of lists in a more sophisticated way.

(a)

[10 points] The quicksort algorithm sorts a list by taking the first element of the list and splitting the list into two lists: those elements which are at most the first element, and those elements which are larger. For example (3 4 2 1 6) would be split into (3 2 1) and (4 6). Then both lists are sorted recursively, yielding (in the example) (1 2 3) and (4 6), and put back together: (1 2 3 4 6). Make sure your base case(s) work(s).

(b)

[Extra credit: 5 points] As above, but instead of choosing the first element of the list as the pivot element (the element according to which elements are put into the first or second list), choose a random element in the list. Remember that (random n) will give you a random number between 0 (inclusive) and n (exclusive).