Use your program to determine the average number of comparisons performed in sorting 1000 arrays for each of the array sizes, 10, 50, 100, 500, 1000, 5000, 10,000, 50,000 and 100,000. For each size, have your code print the average number of comparisons performed on the 1000 arrays of that size and also what the predicted average-case time complexity from the formula.

list_sizes = [10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000]

numberOfLists = 1000 # the number of lists to sort for each list size

numbersOfComparisons = []

...

When your code is finished, create a table, using a spreadsheet or other technology, that has four columns:

Number of Items

Predicted Average Number of Comparisons

Observed Average Number of Comparisons

Percent Difference.

The percent difference from the predicted average would be calculated as (|predictedobserved|)/predicted.