I$)$ Using the induction method, prove the correctness of the Radix Sort algorithm.

$(11)$ Show how to sort n integers in the range $0$ to n$?-1$ in O$($n$)$ time.

$()$ Counting sort can also work efficiently if the input values have fractional parts, but the number of digits in the fractional part is small. Suppose that you are given n numbers in the range $0$ to k$,$ each with at most d decimal $($base $10)$ digits to the right of the decimal point. Modify counting sort to run in $0($n $+109$k$)$ time.