PYTHON 3

**USE RECURSION! **Use no for loops or comprehensions (which include for loops) in your code. Do not call the min or max or sorted functions or the sort method on lists. If you use local variables, each can be assigned a value only once in a call, and it cannot be re-assigned or mutated; try to use no local variables (except where they are mentioned in hints). Of course, do not mutate any parameters. PLEASE HELP WITH THIS PROBLEM (IT'S JUST SOLVING ONE SMALL RECURSION FUNCTION) Define a recursive function named sort; it is passed a list of comparable values as an argument; it returns a new list (constructing a new one, not mutating the argument) with every value in the original list, but ordered in non-descending order. ***SAMPLE OUTPUT: sort([4,5,3,1,2,7,6]) would call separate function (information is below about this function) first, to compute the lists [3,1,2] and [5,7,6](note that 4, the first value in the list, used to do the separation, is not in either list) which when sorted would be [1,2,3] and [5,6,7], resulting in the returned list [1,2,3,4,5,6,7] (the 4 is put in the result list, in the correct place). Your function should run to completion with no noticeable delay. Of course you should not use any built-in Python methods for sorting; you are redefining sort here. You must code the following algorithm. For any non-empty argument list, separate it (hint: call separate from question 1. It is OK to bind the resulting 2-tuple, but never change that binding) into two lists: those with values <= the first value in the list and those with values > the first value; the first value should not appear in the first list, unless there are multiple occurrence of it in the argument list (said another way, the sum of the lengths of the two lists should be one less than the length of the argument list). Note that all the values in the firstlist are strictly < all the values in the second list. Hint:slice. Recursively call sort on each of these two lists and return a single list that contains the sorted values in the first list (the smaller ones), followed by the value used to separate the list, followed by the sorted values in the second list (the larger ones). Again, as in question 1, for the non-base case, first call separate and bind the result (and never change that binding); then determine what result to return,using the binding and recursive calls to sort. You can use + to concatenate lists, but cannot mutate any list (e.g., no calls to append).

***DON'T NEED TO SOLVE*** JUST USE THESE FOR REFERENCE

1. Define a recursive function named separate; it is passed a predicate and a list; it returns a 2- tuple whose 0 index is a list of all the values in the argument list for which the predicate returns True, and whose 1 index is a list of all the values in the argument list for which the predicate returns False.

Calling separate((lambda x:x>=0),[1,-3,-2,4,0,-1,8]) returns ([1,4,0,8],[-3,-2,-1]).