Sorting a sequence in O(n) time [duplicate]

This question already has answers here: 开发者_JS百科 Closed 11 years ago.

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.

---

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.

---

Just use Radix Sort.

---

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

---

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.

---

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.

---

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)

---

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.