$($d$)$ Suppose we are given a set of $n$ distinct natural numbers and that we wish

to sort them. Show how we can encode this sorting problem in terms of the

Convex Hull problem, using $O(n)$ extra work $($i$.$e$.,$ give an $O(n)$ algorithm

to convert any instance of the sorting problem into an instance of the convex

hull problem$).$

$($e$)$ Part $($d$)$ of this question shows that any convex hull algorithm gives rise to a

new algorithm for sorting natural numbers. What does this tell us about the

inherent complexity of the convex hull problem, in terms of lower bounds?

Justify your answer.