# sorting a sorted array that has been inc/dec by random numbers

If given a sorted array of n distinct positive integers. And each element is incremented or decremented by a number between 0 and X. For positive integer X that is a function of n.

Formulate an algorithm that takes the inc/dec array and sort it. Make the run time O(n) when X is constant.

I am unsure with my solution. Firstly, I just choose an random number of buckets... 10. The proof seemed to work out. Is there a way to prove that using X(the variable from above) number of buckets will be better?

In addition, is there a way to utilize the fact the array has been sorted prior to being augmented?

My solution:

1.  Find the minimum and maximum of the array by iteratively going through the array

O(n)

2.  Create intervals for the k buckets (k = number of buckets)
int interval
int k = 10
interval = (Max – Min + 1)/k

3.  Assign each element to the bucket based on the interval
O(n)

4.  Sort each bucket
if there is ni elements in each ith bucket
the sorting using randomized quicksort S(ni) = O(nilogni)

5.  Combine all the elements
O(n)
Runtime Analysis:
•   The time to sort every bucket will be as follows:
•   We assume the elements are uniformly distributed. Thus n/k elements in each bucket.


Since k = n/10, T(n) = n log(10) = O(n)

• Your algorithm is pretty loosely specified. For instance, you define an interval as "(Max - Min + 1)/k", but intervals are usually specified as two numbers. Does that mean the interval size? What are the actual intervals? Another example is step 3, where you assign each element to "the" bucked based on "the" interval. Do you mean that you place each item into "a" bucket? How do you know which one to put it in? Or step 5, "Combine all the elements". How do you combine them? merge sort? How long does that take? – jbapple Mar 9 '16 at 21:08
• The elements are adjusted not by a random amount, but by an arbitrary amount (within the specified range). – Yuval Filmus Mar 9 '16 at 21:37
• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. – D.W. Mar 10 '16 at 19:34

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.
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.