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:
- 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
y are two elements of the input. Variants with
if x <= y or
if cmp(x,y) == -1, etc., are equivalent.
- 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
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.