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

where

M $=$ max

i

xi $$min

i

xi

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