$2.(8$ marks$)$ Quicksort can, in the worst circumstances $($owing to unwise choices of pivot values$),$ perform as poorly for large collections of data as exchange sort. It usually doesn't however, and is frequently described as having an average complexity that is proportional to

n log$2($n$)$

$($That$\text{'}$s n times the log$2$ of n$.)$ log$2$ is described in this week's notes on binary search, as binary search has a time complexity proportional to log$2($n$).$ Scientific calculators frequently have a way of calculating log$2$ of a number, and so does Microsoft Excel. I encourage you to use Excel or some compatible spreadsheet program $($Google Sheets, perhaps$)$ to help you with calculating these logarithms for this problem. For practice, open a new workbook in Excel, put the number $128$ into cell A$1$ and this formula, exactly as shown, into cell B$1$:

$=$log$($a$1,2)$

then press Enter. You should have caused a $7$ to appear in place of the formula in cell B$1.7$ is the log$2$ of $128,$ which is usually written log$2(128),$ and $7$ is also $($not coincidentally$)$ the number of zeroes in the binary for $128$:

$10000000$

Let's repeat the exercise from the previous page, but this time using quicksort instead of exchange sort. For this first part, it will still be you sorting books, and you are still capable of one compare$-$and$-$swap operation per second on average, but now you'll be using n log$2($n$),$ and rounding up to the nearest integer, instead of $($n$2$ n$)/2$ for your middle column calculations. Again, I've done the first one for you.

Number of items $($n$)$ Number of comparisons Sort time in minutes

and seconds $($mm:ss$)$

$103400$:$34$

$12$

$14$

$16$

$18$

$20$

$22$

$24$

Returning to our computer that can make $1000000($one million$)$ comparison$-$and$-$swap operations per second, on average. It is now using quicksort to sort $1000000($one million$)$ items of data. How many days, hours, minutes, and seconds $($d hh:mm:ss$)$ will the computer require to do that?