Sorting a sequence in O(n) time

Question

Possible Duplicate:
Sorting in linear time?

Suppose we are given a sequence S of n elements, each of which is an integer in the range [0,n^2-1]. Can we sort it in O(n) time?

Please dont mind me asking too many interview questions. I am just appetent.

http://stackoverflow.com/questions/749585/sorting-in-linear-time — Tugrul Ates, Mar 21 '11 at 14:06
Did they ask all the questions from the book Programming Pearls? — Prasoon Saurav, Mar 21 '11 at 14:12
are you sure the number of elements is meant to be the same as the number of bits in the largest integer? — jk., Mar 22 '11 at 10:32

Captain Giraffe · Answer 1 · 2012-12-22T15:34:08.690

10

No.

When the only precondition is an integer in the range 0-N².

Counting sorts won't work because the scanning, be it bit-patterns for distinct inputs or buckets for duplicate inputs, would complete in O(N²)
The range would make the key length for radix sort dependent on N hence radix won't work in O(N).

Any statement involving "When N is small" invalidates any O based argument.

edited Dec 22 '12 at 15:34

answered Mar 21 '11 at 14:17

Captain Giraffe

14,407
6
39
67

score 4 · Answer 2 · answered Mar 21 '11 at 14:06

4

Just use Radix Sort.

answered Mar 21 '11 at 14:06

Prasoon Saurav

91,295
49
239
345

1

Radix under these conditions would make the k in Radix O(kN) dependent on N. Not good, and not an answer to OP. – Captain Giraffe Mar 21 '11 at 15:17

score 3 · Answer 3 · edited Mar 22 '11 at 17:11

3

There are O(N) (as opposed to NlogN) sorting algorithms for some special cases where you've got a known, bounded set of objects (e.g. integers in a specified range) :

radix sort

bucket sort

edited Mar 22 '11 at 17:11

answered Mar 21 '11 at 14:07

Steve B.

55,454
12
93
132

2

Yes, but this range has to be also in O(N), which it is not here. – Paŭlo Ebermann Mar 21 '11 at 17:03

score 0 · Answer 4 · answered Mar 21 '11 at 14:03

0

Yes, if we have a hash-like function that for any integer computes its position in the sorted array in O(1) time. However designing such hash-function is IMO problematic - I can't come up with any detailed ideas of how it could work.

answered Mar 21 '11 at 14:03

sharptooth

167,383
100
513
979

How can your hash function decide the position of the value 1 (say) without knowing whether 0 is in S? – dfan Mar 21 '11 at 14:11
@dfan: No idea, that's just a "here's what we need for that" answer. – sharptooth Mar 21 '11 at 14:12
It seems impossible to me, since the position of an integer in the sorted array depends on the values of the other elements in S. – dfan Mar 21 '11 at 14:14

score 0 · Answer 5 · answered Mar 21 '11 at 14:10

0

Programming Pearls covers variations on this problem. If S is large and you can assume that there are no duplicates, the fastest approach is to allocate a bit vector of length n^2, and use it to mark the presence or absence of each number in the range.

answered Mar 21 '11 at 14:10

RossFabricant

12,364
3
41
50

"allocate a bit vector of length n^2" renders the answer to OP a clear no. – Captain Giraffe Mar 21 '11 at 15:15

score 0 · Answer 6 · answered Mar 21 '11 at 14:15

If n is small enough, you can use histogram. Build histogram from input sequence, then construct the output sequence from that histogram. Pseudocode:

H = histogram(input_sequence);
while (not H.empty):
    E = H.smallest_value_element()
    //E.value - value of element, E.count - count in input sequence
    H.remove(E)
    repeat E.count times: output_sequence.append(E.value)

score -2 · Accepted Answer · answered Mar 21 '11 at 14:08

-2

If there are n^2-1 bits of memory available, simply scan the sequence, setting each bit indexed by a value of the sequence to 1. That is O(n) on the size of the sequence. Subsequently, testing for presence is then an O(1) operation.

Of course, if you want to read the sorted sequence out, it's O(n^2), because you need to sweep the entire collection of n^2-1 bits looking for the 1s.

answered Mar 21 '11 at 14:08

joel.neely

30,725
9
56
64

>Of course, if you want to read the sorted sequence out. Isn't this equivalent to say. If you know the algorithm for a problem thats O(1), but if you want to find the answer YMMV. – Captain Giraffe Mar 21 '11 at 14:25
10

Actually producing the sorted sequence seems like a pretty large part of sorting a sequence. I could sort any sequence in zero time, if I am allowed to spend O(n^2) time to later read my sorted sequence out. – dfan Mar 21 '11 at 14:32
Could you explain a little more about this answer? I don't think it is clear on how this results in a sorted sequence of elements. – Sammy Larbi Mar 21 '11 at 14:58
The introductory "if there are n^2-1 bits of memory available" is superflouos. The question is only referring to time constraints, hence there's an arbitrary amount of memory available. If you're a theoretical computer scientist, that is. – Philip Mar 21 '11 at 15:36
@Philip: Every memory bound is trivially also a time bound, as you can't read or write N memory in less than O(N) time. – Paŭlo Ebermann Mar 21 '11 at 17:08
@Paŭlo: Right, but I can write a *fixed* amount of memory in a *constant* amount of time, independent of N. For instance, if I change mergesort to first compute the first 1.000.000 primes and then proceed with mergesort as expected, this doesn't change mergesort's asymptotic runtime of O(n*log n). If there's no memory constraint, memory is infinite. – Philip Mar 22 '11 at 00:08

Sorting a sequence in O(n) time

7 Answers7