sorting a sorted array that has been inc/dec by random numbers
Your algorithm doesn't work since you're analyzing it under some (suspect) random model, whereas the problem setters wanted a worst case guarantee. The worst case for you is that everything falls into the same bucket, and then you just get the usual $O(n\log n)$ guarantee.

Instead of your approach, I suggest trying to use the following observation:


  After sorting, each value moves at most $2X$ positions.


As an example of why this is useful, note that you can find the minimum of the array in time $O(X)$ by looking only at the first $2X$ elements.