Quick sort is generally faster than cither merge sort or heap sort, and usually it requires

only O$($n$($n$))$ memory; however, on occasion, it may require o$($Inn$))$ memory and have a o $($n In$($n$))$

run time. Suppose you implement the following algorithm:

$1.$ If the array size is n $<256,$ use insertion sort;

$2.$ otherwise, if the call stack already has $8$ calls to quick sot on it$,$ call heap sort;

$3.$ otherwise, call quick sort recursively following partition.

Questions:

a$.$ Why does this algorithm run in O$($n In$($n$)$ time even in the worst$-$case scenario for quick sort?

b$.$ Suppose quick$-$sort divides the list into a ratio of $1$:$2$ at each step. How large would n have to be

for heap sort to be called even once? $($