Can you sort n integers in O (n) amortized complexity?

Question

It is theoretically possible to sort an array of n integers in the amortized complexity O (n)?

How about creating the worst case of O (n) complexity?

Most algorithms today are built on O (nlogn) on average + O (n ^ 2) in the worst case. Some, using more memory, are worse than O (nlogn).

Can you create such an algorithm without memory usage? What if your memory is limited? how does it hurt your algorithm?

Answer 1

Any inter-tube page that uses comparison sorts will tell you that you cannot sort faster than O(n lg n) with sort sorts. That is, if your sorting algorithm decides the order by comparing two elements with each other, you cannot do better than this. Examples include quicksort, bubblesort, mergesort.

Some algorithms, such as sorting sorting or bucket sorting or radix sorting, do not use comparisons. Instead, they rely on the properties of the data itself, such as the range of values ​​in the data or the size of the data value.

These algorithms can have more complex complexity. Here is an example script:

You sort 10^6 integers, and each integer is between 0 and 10 . Then you can just count the number of zeros, ones, two, etc. And spit them out in sorted order. This is how the counter works in O(n + m) , where m is the number of values ​​your value can get (in this case, m=11 ).

Other:

You are sorting 10^6 binary strings whose length does not exceed 5 . You can use radix collation to do this: first divide them into 2 buckets depending on their first character, and then collect them for the second character, third, fourth and fifth. As long as each step is stable, you should get a perfectly sorted list in O(nm) , where m is the number of digits or bits at your reference point (in this case m=5 ).

But in the general case, you cannot reliably sort O(n lg n) (using sorting).

Answer 2

I am still not quite happy with the accepted answer. So I return the answer:

It is theoretically possible to sort an array of n integers in the amortized complexity O (n)?

The answer to this question depends on the machine that runs the sorting algorithm. If you have a random access machine that can only work for 1 bit, you can do radix sorting for integers containing no more than k bits, which has already been suggested. Thus, you get O(kn) complexity.
But if you are working on a text computer with a fixed size with a word of at least k bits (which is all consumer computers), the best you can achieve is O(n log n) . This is due to the fact that either log n < k , or you can do a sort count first, and then sort using the O (n log n) algorithm, which will give the first case as well.

How about creating the worst case of O (n) complexity?

It's impossible. The link has already been provided. The idea of ​​the proof is that in order to be able to sort, you have to decide for each element to be sorted, if it is more or less for any other element to be sorted. Using transitivity, this can be represented as a decision tree, which at best has n nodes and log n depth. Therefore, if you want to have better performance than Ω(n log n) , this means removing edges from this decision tree. But if the decision tree is not complete, then how can you make sure that you have made the right decision about some elements a and b ?

Can you create such an algorithm without memory usage?

So, as from above, this is not possible. Therefore, the remaining questions are irrelevant.

Answer 3

If integers are in a limited range, then O (n) “sorting” of them will include the presence of the bit vector “n” bits ... of the loop over the integers and setting n% 8 bits offset n // 8 in this byte array to true. This is the operation "O (n)". Another loop over this bitmap to enumerate / enumerate / return / print all set bits is also an O (n) operation. (Naturally, O (2n) reduces to O (n)).

This is a special case when n is small enough to be inserted into memory or into a file (using the seek () function). This is not a general solution; but this is described in Bentley's “Programming Pearls” --- and was said to be a practical solution to a real problem (involving something like a “freelancing” of phone numbers ... something like: finding the first available phone number that could would be issued to a new subscriber).

(Note: log (10 * 10) is ~ 24 bits to represent all possible integers up to 10 digits in length ... so there is a lot of space in 2 * 31 bits of a typical Unix / Linux maximum memory format).

Answer 4

I believe you are looking for radix sorting .