Question: Linear Time Sorting Problem

[Direwolf007]

Hello, I have been asked to provide an algorithm for the following:

You are given an array of length N, which contains values in the range from 0 to (N^2) - 1. You are to sort it in O(N) time.

I have been unable to find any way to do it, due to the lack of a "hard" upper bound on the input range (Which varies with the size of input).

I'll be happy to hear ideas for anyone who can offer help. Thanks !

[Infarction]

My first thought was a radix sort, but since that does depend on the value of the largest number, I'm don't think that it's strictly O(N) in this case.

[Direwolf007]

I have tried Radix Sort, but since the number of digits is not fixed, it scales with size of input, due to that fact, in this case, the complexity would be O(nlogn), since log(base10)n is the amount of digits.

[Infarction]

Yeah, that's what I was thinking too. Even counting sort depends on the range of values, so it wouldn't fit either. I'm out of ideas, sorry :(

[Direwolf007]

Thanks for the reply, nonetheless.

If anyone else could chime in, I would be rather thankful.

[iamthwee]

http://en.wikipedia.org/wiki/Sorting_algorithm

[Direwolf007]

While I thank you for the reply - I already read the wikipedia entry for that, twice. I also spent a few hours on google, and reading "Introduction To Algorithms" (One of the authors is Cormen, another is Rivest, another is Stein, I don't recall the last one).

Any other ideas folks ?

[thekashyap]

>> You are given an array of length N, which contains values in the range from 0 to (N^2) - 1. You are to sort it in O(N) time.

2 questions to understand the question:

1. Why does the range of value matter? (size/range of value would have no impact on the order of algorithm from what I know)
2. When you say "in O(N) time" do you mean it's an algorithm of order N or you really mean some number of mili/micro/seconds.. ?

[Infarction]

1. It does affect algorithm runtime in several cases, especially when dealing with non-comparison based sorts (since it's proven that comparision based sorts cannot be guaranteed to run in better than O(n log n) time, they don't make the cut for this problem). Look at some of the sorts already mentioned in this thread.

2. Linear time with respect to the length of the input.

[~s.o.s~]

Have you tried out SmoothSort ?

Its best case is O(n) and worst case is O(n log(n)) with the obvious downfall of difficult to implement.

[Infarction]

Since it does have the O(n log n) case, it wouldn't fit the requirements. And I've never seen an implementation of it outside of that paper... ;)

[~s.o.s~]

But practically speaking, a sorting algo having O(n) as its worst case would be hard to get by. I guess the only choice the OP is left with is to pick a nice O(n log(n)) algo and make custom changes to it (depending on the problem statement) to bring it down to O(n) though achieving O(n) for worst case still looks kind of impossible.

And the reason Smoothsort is rarely used is because of the difficulty faced in its implementation.

[Infarction]

Well, in a normal case you'd be able to claim that radix sort, bucket sort, or counting sort (to name a couple) would run in O(n) time. But since they're all dependent on the range in some very small degree, seems like, the claim doesn't hold anymore.

[Direwolf007]

Thanks for the replies guys.

I have tried modifying bucketsort (But there is not guarantee whatsoever that the values will indeed be anywhere near a normal statistical spread over the range, and ofcourse - we already got too many buckets), I tried Radix sort (But since the range is dependant on the input, we have the problem of having the range scale upwards, pushing the running time to O(nlogn), due to the fact that the number of digits is log(base10)n. Countingsort falls through on similar grounds.

I've had the following idea:

What if we create a secondary auxillary array of size N of ints/booleans, which would indicate which elements of the N^2 sized array are used. This would lead to a rather awkward implementation of countsort, where it would not run over the N^2 sized array (but it will allocate and access it - but it will never access more than N of its elements), but would still count and sort the values.

The only thing I am not sure on, is what the allocation of a size N^2 array counts as, complexity wise ?

[Rashakil Fol]

What about something like this:

Make buckets for the ranges 0..n-1, n..2n-1, ..., n^2-n..n^2-1.

Then, first go through the array and fill the buckets with counts of how many elements fall in the buckets (and maybe an array that you fill linearly alongside the count). Then _smartly_ (that's the key) base your strategy on the distribution of the elements in the buckets. (Of course, you'll need to figure out what strategy to use in linear time. But then again, since the counts associated with each bucket can be sorted in linear time using bucket sort.) By the way, you can allocate any amount of memory in constant time.

So maybe with the right smart selection of strategy, you can succeed in linear time.

[Rashakil Fol]

Here's some ideas about strategy: First of all, consider an extreme case, where sqrt(n) buckets have sqrt(n) elements fall into them. Well, know (by induction) that any bucket with more than sqrt(n) elements and n possible values can be sorted in linear time using a recursive call to this same algorithm. The hard part is sorting those buckets in which the range of possible values has length N, but the number of values is much less than N (since this is closer to the general sorting problem).

Consider another extreme case. Suppose we get n/log(n) buckets of size log(n). Then each of these buckets can be sorted in log(n)(log(log(n)) time, which makes the total running time n*log(log(n)). That's obviously not the right algorithm to use, but it's much better than n*log(n).

Well, what _can_ we do? If we're to sort each of these buckets separately, we'll need to sort them in log(n) time (which is linear with respect to size).

And in general, if we consider the cases where we get n/f(n) buckets containing approximately f(n) elements each, then sorting these buckets naively will give overall n * log(f(n)) time. In "average" cases, we'll have a long tail of buckets with 2,1, and 0 elements, which means average case will take O(n) overall running time. But if f = log, then we get nlog(log(n)). And if f(n) = sqrt(n)/log(n), we get n*log(n) running time... But if f(n) = sqrt(n) or higher, then all of the sudden we get to call our algorithm recursively and get O(n) overall time. (And of course we're assuming we can get a way for our algorithm to be linear in the other cases.)

But then to solve the log(n) case, we'll need a way to sort (generally speaking) n elements in the range 1..e^n in O(n) time... And to solve the f(n) case, we'll need a way for 1..f^-1(n) in O(n) time. So ignore my previous post; this attack is going nowhere.

[Rashakil Fol]

Are you sure you don't need to provide O(N) _average_ time?

[Direwolf007]

Are you sure you don't need to provide O(N) _average_ time?

Yes, I am positive. I needs to be O(n) in the worst case.

[Infarction]

hm... just an idea... what if you tried applying any of the otherwise O(n) algorithms, but took the sqrt of the data as you sorted it. That would cut out the polynomial range, leavning you from 0..N, which is then polynomial time. You'd have to make an extra run over the loop at the end to square everything back to it's actual value.

[~s.o.s~]

Nope, won't do, unless he is ready to sacrifice the real values and accept the approximates. Think of it this way, would the data before squaring and after squaring be the same? I guess no. If you know the way floating point numbers are handled by the system, you would know what I am trying to convey.