<p>Generally speaking, you <em>can</em> sort n numbers where each is given by O(log n) bits using time that is <em>linear</em> in the input size (i.e. O(nlogn)) using something like radix sort (but you may need to be careful about the exact model of computation -- and I don't know the details of which models admit such linear time algorithms).  </p>

CC BY-SA 2.5
2010-10-14T21:39:38.813Z
Which models admit fast algorithms seems like a question where there may not be consensus: http://blog.computationalcomplexity.org/2009/05/shaving-logs-with-unit-cost.html
Aaron Sterling
CC BY-SA 2.5
2010-10-14T21:42:42.647Z
Maybe, but as I said to Charles, those kind of algorithms use meta information about the input. There, the fact that they are numbers. I was looking for a general sort algorithm, ie without other information than the comparison function.
Ludovic Patey
CC BY-SA 2.5
2010-10-14T21:32:16.827Z
2010-10-14T21:32:16.827Z
Noam
<p>There are many examples of $o(n\log n)$ sorting in the literature.  For example,</p>

<ul>
<li>Han, Y. and Thorup, M. 2002. Integer sorting in $O\left(n\sqrt{\log\log n}\right)$ expected time and linear space. <a href="http://www.csee.umkc.edu/~hanyij/research/focs02.ps" rel="nofollow">http://www.csee.umkc.edu/~hanyij/research/focs02.ps</a></li>
<li>Y. Han. Deterministic sorting in $O\left(n\log\log n\right)$ time and linear space.</li>
</ul>

CC BY-SA 2.5
2010-10-14T20:57:58.760Z
I think all algorithms known in < n log n cheat by using meta informations on the input list, or it isn't complexity in the worst case.
Ludovic Patey
CC BY-SA 2.5
2010-10-14T22:54:43.590Z
These solve more restricted problems than a general comparison sort does and are thus able to go faster.  No comparison sort can exceed lg(n!) = Omega(n log n) in the worst case.
Charles
CC BY-SA 2.5
2010-10-14T20:34:12.847Z
2010-10-14T20:34:12.847Z
Charles
<p>Another example is <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6WJ0-4B4RP4X-JK&amp;_user=10&amp;_coverDate=12%2F31%2F1993&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_origin=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1499128860&amp;_rerunOrigin=google&amp;_acct=C000050221&amp;_version=1&amp;_urlVersion=0&amp;_userid=10&amp;md5=2693164491cf1bfe1c244e2196fb9b70&amp;searchtype=a" rel="nofollow">Fredman and Willard (1993), Surpassing the information theoretic bound with fusion trees.</a></p>

CC BY-SA 2.5
2010-10-15T07:20:02.647Z
2010-10-15T07:20:02.647Z
mitanyen
<p>I think you are confusing the size of the input with the number of elements in the input. The time complexity of sorting algorithms is defined in terms of the number of comparisons based on the number of elements, not on the size of the inputs, so when you say that it costs $n \log^2 n$ to sort the elements you are already saying that your algorithm is worst than $O(n\log n)$.</p>

CC BY-SA 2.5
2010-10-15T14:26:36.313Z
It was the purpose of my question : the difference of size between input and the number of elements which could make complexity lower than O(n log n) in complexity theory.
Ludovic Patey
CC BY-SA 2.5
2010-10-14T20:34:06.280Z
2010-10-14T20:39:08.953Z
2010-10-14T20:39:08.953Z
Dave Clarke
<p>Without looking at any details, why do your say your algorithm beats $O(N\log N)$?</p>

<p>In your notation, $N\log N = n\log n\log(n\log n) = n\log n\log n + n\log n\log\log n = O(n\log^2n)$.</p>

<p>No contradiction.</p>

CC BY-SA 2.5
2010-10-14T20:54:39.340Z
That's true, sorry. But couldn't we try to use the fact that comparisons are bitwise to try to "group" them by any way even if the order of the objects isn't the same as the order induced by the binary representation ?
Ludovic Patey
CC BY-SA 2.5
2010-10-14T21:15:01.177Z
I'm not sure what you mean.
Lev Reyzin
CC BY-SA 2.5
2010-10-14T21:28:12.343Z
All I mean is that as comparisons are in log n, they aren't in one step, and thus substeps could be mutualised between comparisons and so reduce their number.
Ludovic Patey
CC BY-SA 2.5
2010-10-15T12:20:54.323Z
Often, the O(nlogn) lower bounds assume an input of size n and unit comparison costs.  In that case there's nothing to play with.  In general, even if you're counting bits, I doubt you can win much.
Lev Reyzin
CC BY-SA 2.5
2010-10-14T20:43:07.930Z
2010-10-14T20:50:26.767Z
2010-10-14T20:50:26.767Z
Lev Reyzin
<p>If we consider literature, sorting algorithms are based only on number of comparisons needed to sort a list of size n, considering that n is the size of the input.</p>

<p>But if we want to encode input, we can't encode each object of the list into a fixed-size binary representation because hence, we would consider that the domain of the objects is fixed and thus, I think we could find better sorting algorithms by precomputing some stuff in the Turing Machine.</p>

<p>If we consider that the domain isn't fixed, we have to encode each of our items into a $\log(n)$-size representation. Thus the input is of size $N = n\log(n)$. But as our numbers are of variable length, then we can consider that comparison has a cost of $\log(n)$, but even with this, if we apply a reasonable sorting algorithm (ie an $n \log n$ algorithm), the algorithm will take $n \log^2(n)$ time in a Turing machine, where $n$ is the number of objects, but where $n \log n$ is the size of our input. In this case, we have an algorithm of complexity lower than $O(N \log(N))$ where $N$ is the size of the input.</p>

<p>Is there a mistake?</p>

<cc.complexity-theory><ds.algorithms><sorting>
Sorting algorithm with a complexity smaller than $n \log n$?
Ludovic Patey
# Sorting algorithm with a complexity smaller than $n \log n$?

(Asked by: username_0 on 2010-10-14)

If we consider literature, sorting algorithms are based only on number of comparisons needed to sort a list of size n, considering that n is the size of the input.

But if we want to encode input, we can't encode each object of the list into a fixed-size binary representation because hence, we would consider that the domain of the objects is fixed and thus, I think we could find better sorting algorithms by precomputing some stuff in the Turing Machine.

If we consider that the domain isn't fixed, we have to encode each of our items into a $\log(n)$-size representation. Thus the input is of size $N = n\log(n)$. But as our numbers are of variable length, then we can consider that comparison has a cost of $\log(n)$, but even with this, if we apply a reasonable sorting algorithm (ie an $n \log n$ algorithm), the algorithm will take $n \log^2(n)$ time in a Turing machine, where $n$ is the number of objects, but where $n \log n$ is the size of our input. In this case, we have an algorithm of complexity lower than $O(N \log(N))$ where $N$ is the size of the input.

Is there a mistake?

**Tags:** cc.complexity-theory, ds.algorithms, sorting


---

## 5 answers

### Answer by username_6 on 2010-10-14. Score: 10 | Accepted answer

Without looking at any details, why do your say your algorithm beats $O(N\log N)$?

In your notation, $N\log N = n\log n\log(n\log n) = n\log n\log n + n\log n\log\log n = O(n\log^2n)$.

No contradiction.

> **Comments:**
> **username_0**: That's true, sorry. But couldn't we try to use the fact that comparisons are bitwise to try to "group" them by any way even if the order of the objects isn't the same as the order induced by the binary representation ?  
> **username_6**: I'm not sure what you mean.  
> **username_0**: All I mean is that as comparisons are in log n, they aren't in one step, and thus substeps could be mutualised between comparisons and so reduce their number.  
> **username_6**: Often, the O(nlogn) lower bounds assume an input of size n and unit comparison costs.  In that case there's nothing to play with.  In general, even if you're counting bits, I doubt you can win much.  

---

### Answer by username_1 on 2010-10-14. Score: 8

Generally speaking, you *can* sort n numbers where each is given by O(log n) bits using time that is *linear* in the input size (i.e. O(nlogn)) using something like radix sort (but you may need to be careful about the exact model of computation -- and I don't know the details of which models admit such linear time algorithms).

> **Comments:**
> **username_2**: Which models admit fast algorithms seems like a question where there may not be consensus: http://blog.computationalcomplexity.org/2009/05/shaving-logs-with-unit-cost.html  
> **username_0**: Maybe, but as I said to username_3, those kind of algorithms use meta information about the input. There, the fact that they are numbers. I was looking for a general sort algorithm, ie without other information than the comparison function.  

---

### Answer by username_3 on 2010-10-14. Score: 5

There are many examples of $o(n\log n)$ sorting in the literature. For example,

* Han, Y. and Thorup, M. 2002. Integer sorting in $O\left(n\sqrt{\log\log n}\right)$ expected time and linear space. <http://www.csee.umkc.edu/~hanyij/research/focs02.ps>
* Y. Han. Deterministic sorting in $O\left(n\log\log n\right)$ time and linear space.

> **Comments:**
> **username_0**: I think all algorithms known in < n log n cheat by using meta informations on the input list, or it isn't complexity in the worst case.  
> **username_3**: These solve more restricted problems than a general comparison sort does and are thus able to go faster.  No comparison sort can exceed lg(n!) = Omega(n log n) in the worst case.  

---

### Answer by username_4 on 2010-10-15. Score: 3

Another example is [Fredman and Willard (1993), Surpassing the information theoretic bound with fusion trees.](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WJ0-4B4RP4X-JK&_user=10&_coverDate=12%2F31%2F1993&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1499128860&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=2693164491cf1bfe1c244e2196fb9b70&searchtype=a)


---

### Answer by username_5 on 2010-10-14. Score: 3

I think you are confusing the size of the input with the number of elements in the input. The time complexity of sorting algorithms is defined in terms of the number of comparisons based on the number of elements, not on the size of the inputs, so when you say that it costs $n \log^2 n$ to sort the elements you are already saying that your algorithm is worst than $O(n\log n)$.

> **Comments:**
> **username_0**: It was the purpose of my question : the difference of size between input and the number of elements which could make complexity lower than O(n log n) in complexity theory.  

---

