$(2)$ Suppose we are given a list L of n positive integers each of whose

value is in the range $0($n$^21).$ The problem is to sort the integers.

$($a$)$ Analyze and determine the complexity of the following algorithm: copy

the content of list L into array A$[1]$ A$[$n$]$ and sort A using merge$-$sort.

$($b$)$ Analyze and determine the complexity of the following algorithm: set

up a bin $($queue$)$ for each of the possible values in $0($n$^21)$ and use

bin$-$sort to sort L$.$

$($c$)$ Suppose x is an integer whose value is in the range $0(10^31),$ then

clearly $3$ digits are enough to represent x in base $10($i$.$e$.,$ digits are

$0,1,2,9).$

Suppose x is an integer whose value is in the range $0($n$^21).$ Then,

how many digits in base n are sufficient to represent x$?$ Justify briefly.

$($d$)$ Outline an algorithm to sort L in O$($n$)$ time.