I see some algorithms can do sorting in O(nloglogn) time. Is it reasonable to assume that as research progresses, more and more will be done to logarithm the extra time e.g. next research will produce an algorithm that is O(nlogloglogn) and so on and therefore in the limit sorting could be done in linear time or is there a proof that it can't be done as close to linear time as possible?

What are the charactaristics of a set that a very fast e.g. O(nloglogn) algorithm can sort? Are these fast algorthms as general as quicksort or only for very special sets?

Is O(nloglogn) still the fastest (it was the fastest in 2000)?

Thank you

In defense of the question

If I have one comparator circuit per element, why would it not be direct i.e. O(1) ?

  • 7
    $\begingroup$ The fastest algorithm to sort "oh whatever" requires $\Theta(n\log n)$ comparisons. The only way to beat this bound is to sort something specific in a more powerful model than decision trees. The $O(n\log\log n)$ bound you cite is for sorting integers in the integer RAM. Not "oh, let's say integers" but "INTEGERS DAMMIT". $\endgroup$
    – Jeffε
    Jun 11 '12 at 14:19
  • 5
    $\begingroup$ Once you specify the problem, the model, and demonstrate understanding of the basis concepts (like the difference between sorting integers and sorting in general, or the difference between integer RAM and decision trees) then you are asking a real question. $\endgroup$ Jun 11 '12 at 15:07
  • 7
    $\begingroup$ In particular, you would need to demonstrate that "sorting in general" can be solved in any model other than comparison trees, in which the exact complexity (up to lower-order terms) has been known for decades. $\endgroup$
    – Jeffε
    Jun 11 '12 at 15:11
  • 6
    $\begingroup$ @NickRosencrantz: It's not clear whether you're familiar with the rather large literature on sorting methods. as commmenters have pointed out, the speed of sorting algorithms depends critically on what operations you can assume: it might be best to go back and look over some of these bounds before you frame the question. $\endgroup$ Jun 11 '12 at 15:14
  • 4
    $\begingroup$ @NickRosencrantz If you ask on a research site, you do need to prove that you're familiar with the classical literature on the topic. Taking things for granted is not a good idea; you need to look closer at underlying assumptions to understand what's going on. Suresh is not lying, but telling you what wrong assumptions underlie your question. Your unwarranted accusation fails the Stack Exchange directive to be nice. $\endgroup$ Jun 11 '12 at 22:29

(Hope the question can be migrated to cs.SE even though I am posting an answer? I am only answering rather than commenting because of the length of what I am writing)

Ok, let me try to clarify this. Say the model of computation is the C language, and elementary C operations (basic arithmetic, dereferencing a pointer, shifting left and right, etc.) take time 1. The (various flavors) of the RAM machine are abstractions of this "C language model". You could try to do one of two things:

  1. Implement a function sort (like C's qsort) that takes as input an array of pointers to any arbitrary set of $n$ objects (say $n$ is also part of the input). That is nice because it's very general, i.e. it gives the user/programmer a single function for all his sorting needs. But because sort does not know apriori what objects it is dealing with, it does not even know when they are sorted. So you need to somehow tell sort about these objects. The standard way is to pass to sort a pointer to a compare function (i.e. compare(obj1, obj2) returns 1 if obj1 is greater than obj2 in the sorted order, for example). If this will be the design you follow for sort, then you are in the decision tree model world, and provably sort will need to call compare at lest $\Theta(n \log n)$ times. You might try to tell sort about its set of objects in some other way, but it is not clear what that would be. Also, if your method is general enough to work with arbitrary sets of objects, it will likely hit the $\Theta(n \log n)$ barrier again.

  2. Implement a function sortInteger that takes an array of say long int, because you know that you will be sorting integers that fit in a single machine word (i.e. are in the range of long int). Now you can use the algorithm from the paper you referred to and that algorithm will take $O(n \log \log n)$ time (i.e. make that many elementary C operations). But sortInteger will only work correctly if it is passed an array of long int, to be sorted in the natural order (Note: the algorithm will still be correct and run in time $O(n \log \log n)$ if the size of long grows with the years; in fact that is an implicit assumption for the asymptotic analysis here). Now afaik, it is consistent with current knowledge that there exists some algorithm that you can use for sortInteger that takes linear time. But keep in mind that computer science has had zero success in showing that any problem takes more than linear time in the "C language model" (aside from some dynamic data structure problems). So do not read too much into "we don't know if $n$ integers that each fit in a single computer word can be sorted in linear time."

Also, if you are ok with randomized algorithms, there is an improvement by Han and Thorup, who show how to sort $n$ integers that each fit in a single computer word in expected time $O(n \sqrt{\log \log n})$.


Comparison sorts cannot be linear

It depends what you're sorting and how you're sorting it, but under the most common model, an $O(n\,\log \log n)$ sorting algorithm is impossible. The most common model of sorting is the following, called a comparison sort:

  1. The order of element can only be determined by comparing two elements. More precisely, the only possible operations on the input elements take two elements and return a result that depends only on their relative order and not on the rest of the input. Typically, the algorithm can contain if x < y then … else … where x and y are two elements of the input. Variants with if x <= y or if cmp(x,y) == -1, etc., are equivalent.
  2. Nothing is known beforehand about the input data. In particular, the elements may be all distinct.

The worst case of a comparison sort is always $\Omega(n\,\log n)$. This is not something that can be improved by further research: it is a mathematical theorem. The sketch of the proof is as follows: given $n$ input elements, there are $n!$ (factorial $n$) permutations of these elements, only one of which is sorted (when the elements are all distinct, which can happen by hypothesis 2). The sorting algorithm must work for all possible permutations of the input, so it must have $n!$ different possible executions. If the algorithm makes at most $k$ comparisons (which by hypothesis 1 is the only way to distinguish between inputs that must be sorted differently), then there are at most $2^k$ possible different executions. Therefore $n! \le 2^k$, i.e. $k \ge \log_2 (n!)$. It is known that $\log_2 (n!) = \Omega(n \log n)$ (it's a consequence of Stirling's approximation). Hence $k = \Omega(n \log n)$, i.e. the sorting algorithm must make at least $\Omega(n \log n)$ comparisons in the worst case.

There are well-known $O(n \log n)$ sorting algorithms on arrays and lists (heap sort, merge sort). Hence $\Theta(n \log n)$ is the best worst-case bound for a comparison sort on an array or a list.

If you look at average-case time complexity, you still can't do better than $\Omega(n \log n)$ if all permutations of the input are equiprobable. On the other hand, if you allow different permutations to have different probabilities, you can get a linear sort on average — with assumptions like “the input is already sorted with probability $1 - 1/n^2$”.

Other models of sorting

It is possible to have a $O(n\,\log \log n)$ or linear or even better sorting algorithm if you relax the assumptions.

If you allow very exotic models, such as “wave a magic wand” or “the only valid input is already sorted”, then $O(1)$ is possible. Any model that allows $O(1)$ sorting is not likely to be useful.

If you allow “return the smallest input element” as a primitive (which invalidates hypothesis 1), bounded-time operation, then selection sort has a linear running time.

If there is a finite bound on the number of distinct input elements, then a linear-time sort is possible. For example, if the input consists only of 0's and 1's, then you can put all the 0's before all the 1's in linear time. Radix sort generalizes this to input data that are $m$-bit strings: it has a run time of $\Theta(n \, m)$. With a fixed $m$ (i.e. a fixed finite input domain), this is linear in the number of inputs.


Not the answer you're looking for? Browse other questions tagged or ask your own question.