Write a function to do a quicksort on a list.

Question

Note: This is by far the most difficult of the sorts to implement, as it involves recursion. The choice of using a random index for the partition allows for fewer lines of code, as otherwise there are a number of special cases. For example, if an implementation always chose the middle, then it could run into infinite recusion if the list were (13, 2, 8), as everything would continue to be split into the larger list.

Answer 1

```
import random
def quickSort(list, depth):
depth+=1
newList = []
if len(list)>1:
partitions = partition(list)
partial = quickSort(partitions[0], depth)
partial2= quickSort(partitions[1], depth)
for p in partial:
newList.append(p)
for p in partial2:
newList.append(p)
else:
return list
return newList
def partition(list):
pivotIndex = random.choice(range(0, len(list)))
pivotValue = list[pivotIndex]
smallList = []
largeList = []
for i in range(0, len(list)):
if list[i] smallList.append(list[i])
else:
largeList.append(list[i])
return (smallList, largeList)
```