$(15$ pts$.)$ Sorting Lower Bound. Show that any array of integers $x[1$dotsn$]$ can be sorted in $O(n+M)$ time, where

$M=ma{x}_i{x}_i-mi{n}_i{x}_i$

For small $M,$ this is linear time: why doesn't the $(nlogn)$ lower bound apply in this case?

$3.(15$ pts$.)$ Binary search.