In this programming exercise you will perform an empirical analysis of the QuickSort algorithm to study the actual average case behavior and compare it to the mathematically predicted behavior. That is, you will write Python code that counts the number of comparisons performed by QuickSort on an array of a given size. You will run the program on a large number of arrays of a certain size and determine the average number of comparisons performed. You will do this for several different sizes and compare the observed results with what is expected.

In the cells below, implement the version of **_QuickSort_** and **_Partition_**. Make sure your functions are appropriately documented.

(Replace the three dots with your code.)

def QuickSort(L, a, b):

''' Arranges the elements of L between indices a and b in nondescending order '''

...

def Partition(L, a, b):

''' Rearranges the elements of L between indices a and b so that all elements

smaller than L[a] lie to the left of L[a]'s new index and all

elements larger than or equal to L[a] lie to the right

then retruns L[a]'s' new index.'''

...