We know that Python provides the function sorted$()$ which can be used to sort a list. But we have not seen how this

function works "underneath the hood". There are many possible sorting algorithms that can be used to sort a list. In this

problem we will explore a recursive sorting algorithm named Quicksort.

Your solution in this problem should NOT make use of the functions sort$()$ or sorted$().$ In fact, the only built$-$in

functions or methods it should use are len$()$ and append$().$

In this problem, you will write a function named quicksort$()$ with one parameter named x$,$ which is assumed to be a list

of values of a single data type. The function should create and return a sorted copy of x$.$ The function will select an element

of x to act as a "pivot" upon which the list will be split. All elements of x less than the pivot will go into a list named low and

all elements greater than or equal to the pivot will go into a list named high. The quicksort$()$ function will then be

recursively applied to the lists low and high.

Write a function quicksort$()$ that accepts a single parameter named x$.$

The function should return a sorted copy of x by performing the following steps:

$1.$ First check to see if the length of x is less than or equal to $1.$ If so$,$ return x$.$

$2.$ Set pivot equal to the first element of x$.$

$3.$ Store pivot in a single$-$element list named mid and create empty lists named low and high.

$4.$ Loop over all elements of x EXCEPT for the first element $($which is the pivot$).$ For each such element, if that

element is less than the pivot, then append it to low, otherwise append it to high.

$5.$ Call quicksort$()$ on low, storing the result in a variable named sorted$\_$low.

$6.$ Call quicksort$()$ on high, storing the result in a variable named sorted$\_$high.

$7.$ Concatenate sorted$\_$low, mid, and sorted$\_$high into a single list, and then return the result.

We will now test this function on a randomly generated list.

In a new code cell, create a randomly generated list using the following line of code:

random.seed$(2)$

random$\_$list$\_2=$ random.choices$($range$(100),$ k$=20)$

Print random$\_$list$\_2.$ Then call quicksort$()$ on random$\_$list$\_2$ and print the list returned by that function.

We will test the function on a second randomly generated list.

In a new code cell, create a randomly generated list using the following line of code:

random.seed$(3)$

random$\_$list$\_3=$ random.choices$($range$(100),$ k$=20)$

Print random$\_$list$\_3.$ Then call quicksort$()$ on random$\_$list$\_3$ and print the list returned by that function