<h3>Comparison sorts cannot be linear</h3>

<p>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 <strong>impossible</strong>. The most common model of sorting is the following, called a <a href="http://en.wikipedia.org/wiki/Comparison_sort">comparison sort</a>:</p>

<ol>
<li>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 <code>if x &lt; y then … else …</code> where <code>x</code> and <code>y</code> are two elements of the input. Variants with <code>if x &lt;= y</code> or <code>if cmp(x,y) == -1</code>, etc., are equivalent.</li>
<li>Nothing is known beforehand about the input data. In particular, the elements may be all distinct.</li>
</ol>

<p>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 <a href="http://en.wikipedia.org/wiki/Stirling%27s_approximation">Stirling's approximation</a>). Hence $k = \Omega(n \log n)$, i.e. the sorting algorithm must make at least $\Omega(n \log n)$ comparisons in the worst case.</p>

<p>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.</p>

<p>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$”.</p>

<h3>Other models of sorting</h3>

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

<p>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.</p>

<p>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.</p>

<p>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 <code>0</code>'s and <code>1</code>'s, then you can put all the <code>0</code>'s before all the <code>1</code>'s in linear time. <a href="http://en.wikipedia.org/wiki/Radix_sort">Radix sort</a> 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.</p>

CC BY-SA 3.0
2012-06-11T21:50:09.143Z
2012-06-11T21:50:09.143Z
Gilles 'SO- stop being evil'
<p>(<em>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</em>)</p>

<p>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:</p>

<ol>
<li><p>Implement a function <code>sort</code> (like C's <code>qsort</code>) that takes as input an array of pointers to <em>any arbitrary set of $n$ objects</em> (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 <code>sort</code> 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 <code>sort</code> about these objects. The standard way is to pass to <code>sort</code> a pointer to a <code>compare</code> function (i.e. <code>compare(obj1, obj2)</code> returns 1 if obj1 is greater than obj2 in the sorted order, for example). If this will be the design you follow for <code>sort</code>, then you are in the decision tree model world, and provably <code>sort</code> will need to call <code>compare</code> at lest $\Theta(n \log n)$ times. You might try to tell <code>sort</code> 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.</p></li>
<li><p>Implement a function <code>sortInteger</code> that takes an array of say <code>long int</code>, because you know that you will be sorting integers that fit in a single machine word (i.e. are in the range of <code>long int</code>). Now you can use the algorithm <a href="http://www.sciencedirect.com/science/article/pii/S002200009891580X">from the paper you referred to</a> and that algorithm will take $O(n \log \log n)$ time (i.e. make that many elementary C operations). But <code>sortInteger</code> will <strong>only</strong> work correctly if it is passed an array of <code>long int</code>, 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 <code>long</code> 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 <code>sortInteger</code> 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."</p></li>
</ol>

<p>Also, if you are ok with randomized algorithms, there is an <a href="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1181890">improvement</a> 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})$. </p>

CC BY-SA 3.0
2012-06-11T20:04:29.587Z
2012-06-11T22:14:40.790Z
2012-06-11T22:14:40.790Z
Sasho Nikolov
<p>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?</p>

<p>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?</p>

<p>Is O(nloglogn) still the fastest (it was the fastest in 2000)?</p>

<p>Thank you</p>

<h2>In defense of the question</h2>

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

CC BY-SA 3.0
2012-06-11T13:42:02.387Z
Sorting what (presumably integers?), in which model?
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-11T13:47:17.543Z
Say integers since it's easiest to understand and they have a natural sorting order. The model we can use is the von Neuman computer if that qualifies as a model we can use.
Niklas Rosencrantz
CC BY-SA 3.0
2012-06-11T14:09:28.330Z
No, it does not count as a model.  What is the model used in the work you cited?  I am surprised to hear that integers without bounds can be sorted in time O(n log log n) (in any reasonable model), but I am not familiar with recent advances in sorting algorithms.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-11T14:19:51.753Z
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".
Jeffε
CC BY-SA 3.0
2012-06-11T14:30:25.417Z
How do you mean a computer sorts anything else than integers? Source http://www.drdobbs.com/architecture-and-design/184404062 I was wondering whether the article is outdated and it says this depends on a lot of things but it doesn't mention the model. Of course since it's theory there must be a model and when this is computer science theory, can you really expect that I'm asking about anything else than integers? What would that be that a computer can sort that is not an integer? It's usually 0 Volts or 12 Volts or that is really what a computer is sorting and not abstract algebra.
Niklas Rosencrantz
CC BY-SA 3.0
2012-06-11T14:37:21.430Z
by integers @JɛﬀE means integers with the natural ordering on them. You can sort whatever you want with an arbitrary binary relationship, however if you are sorting some other data structure you might actual say that $0101 > 0111$ because of what objects they encode and what the induced ordering on the bit strings becomes. I have voted to close this question as off-topic because it is _not research level_, try [CS.SE](http://cs.stackexchange.com/) to familiarize yourself with the basics of theory.
Artem Kaznatcheev
CC BY-SA 3.0
2012-06-11T14:48:24.503Z
Since when is upper bounds for sorting in general not research level? You're wrong. It is research level since you can't prove there is not a faster algorithm.
Niklas Rosencrantz
CC BY-SA 3.0
2012-06-11T15:07:08.477Z
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.
Artem Kaznatcheev
CC BY-SA 3.0
2012-06-11T15:11:05.927Z
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.
Jeffε
CC BY-SA 3.0
2012-06-11T15:14:48.107Z
@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.
Suresh Venkat
CC BY-SA 3.0
2012-06-11T15:15:28.840Z
Really? This article by a CS professor says that we don't know whether O(nlogn) like in binary search is the fastest drdobbs.com/architecture-and-design/184404062  Did you read the article? If O(nlogn) is the fastest then binary tree would be the fastest always and there would be no need for structures such as B+ etc. For special cases there definitely should be faster cases than O(nlogn) and it seems the article that I link to here is saying that we don't know whether sorting can approach O(n) instead of staying at O(nlogn)
Niklas Rosencrantz
CC BY-SA 3.0
2012-06-11T15:18:52.860Z
Why not take for granted the structure is like an array with typical array methods since it's common computer science to use arrays and we use them everywhere else. Can't you guess even think that I'm using an array? Why do I need to prove that I'm familiar with sorting literature to ask this question? I also thought binary search was the fastest until I saw these algorithms could do O(nloglogn) and my question is if O(nlogloglog...logn) could be possible and then you saynothing is possible which is you lying to me here.
Niklas Rosencrantz
CC BY-SA 3.0
2012-06-11T22:29:03.317Z
@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](http://cstheory.stackexchange.com/faq#etiquette).
Gilles 'SO- stop being evil'
CC BY-SA 3.0
2013-01-21T00:23:26.467Z
If I have one comparator circuit per element, why would it not be direct?
Niklas Rosencrantz
CC BY-SA 3.0
2013-01-21T02:26:25.737Z
I am closing this question. As it stands the question is off-topic. Please read the [faq] to  understand the scope of this site, questions like this would probably be more suitable for [cs.se] which has a broader scope.
Kaveh
CC BY-SA 3.0
2013-01-21T03:23:19.907Z
@Kaveh I understand "just checking" would be linear. But checking a solution can be slower than arranging it, don't you think?
Niklas Rosencrantz
CC BY-SA 3.0
2013-01-21T03:34:24.307Z
@Nick, did you read my comment?
Kaveh
CC BY-SA 3.0
2013-01-21T03:36:28.577Z
@Kaveh I even own the book you mentioned ("Intro to algorithms).
Niklas Rosencrantz
CC BY-SA 3.0
2013-01-21T04:24:45.483Z
@Nick, did you read the [faq]?
Kaveh
CC BY-SA 3.0
2013-01-21T08:11:02.203Z
@Kaveh Here's O(nloglogn) http://www.nada.kth.se/~snilsson/software/nloglogn.c
Niklas Rosencrantz
CC BY-SA 3.0
2013-01-21T08:36:11.130Z
@Nick, I have seen that. I still think this is off-topic here. Let me explain why: the target community for this site are professional researchers in theoretical computer science (professors, post-docs, graduate students, and other researchers in research labs, etc.). As such we expect the questions on this site to be relevant to such people. I think your question is off-topic here because of this. The motivation for questions here are normally researching. One can make a research-level question of this, but you haven't stated the question so and you haven't shown that you know the basics.
Kaveh
CC BY-SA 3.0
2013-01-21T08:40:22.540Z
You have seen a post on a site and wanted to see if that is still the best known algorithm and there is nothing wrong with that by itself. However it doesn't really belong here and seems more suitable for [cs.se] which has a more general audience. It could have been an acceptable boarder case question if the question was stated *clearly* and *rigorously* with a reference to the paper but it wasn't. Many of users here also participate on [cs.se] and answer more general level question there, but the scope of this site is more restricted as explained in the [faq].
Kaveh
CC BY-SA 3.0
2013-01-21T10:07:38.230Z
@Kaveh It's not far fetched that O(nloglogn) will develop to O(nlogloglogn) and so on towards linear. The paper even mentions linear sorting. The paper is exactly the background and was the CS site even online when I posted this question to begin with? I didn't know there was a CS site until recently, of course I will thoroughly consider where and what to post. I thought the title of the paper was interesting ("linear sorting") and then you just block that.
Niklas Rosencrantz
<ds.algorithms><time-complexity><sorting>
Are sorting algorithms approaching linear time?
Niklas Rosencrantz
# Are sorting algorithms approaching linear time?

(Asked by: username_0 on 2012-06-11)

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) ?

**Tags:** ds.algorithms, time-complexity, sorting
> **Comments:**
> **username_1**: Sorting what (presumably integers?), in which model?  
> **username_0**: Say integers since it's easiest to understand and they have a natural sorting order. The model we can use is the von Neuman computer if that qualifies as a model we can use.  
> **username_1**: No, it does not count as a model.  What is the model used in the work you cited?  I am surprised to hear that integers without bounds can be sorted in time O(n log log n) (in any reasonable model), but I am not familiar with recent advances in sorting algorithms.  
> **username_2**: 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".  
> **username_0**: How do you mean a computer sorts anything else than integers? Source http://www.drdobbs.com/architecture-and-design/184404062 I was wondering whether the article is outdated and it says this depends on a lot of things but it doesn't mention the model. Of course since it's theory there must be a model and when this is computer science theory, can you really expect that I'm asking about anything else than integers? What would that be that a computer can sort that is not an integer? It's usually 0 Volts or 12 Volts or that is really what a computer is sorting and not abstract algebra.  
> **username_3**: by integers @JɛﬀE means integers with the natural ordering on them. You can sort whatever you want with an arbitrary binary relationship, however if you are sorting some other data structure you might actual say that $0101 > 0111$ because of what objects they encode and what the induced ordering on the bit strings becomes. I have voted to close this question as off-topic because it is _not research level_, try [CS.SE](http://cs.stackexchange.com/) to familiarize yourself with the basics of theory.  
> **username_0**: Since when is upper bounds for sorting in general not research level? You're wrong. It is research level since you can't prove there is not a faster algorithm.  
> **username_3**: 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.  
> **username_2**: 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.  
> **username_4**: @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.  
> **username_0**: Really? This article by a CS professor says that we don't know whether O(nlogn) like in binary search is the fastest drdobbs.com/architecture-and-design/184404062  Did you read the article? If O(nlogn) is the fastest then binary tree would be the fastest always and there would be no need for structures such as B+ etc. For special cases there definitely should be faster cases than O(nlogn) and it seems the article that I link to here is saying that we don't know whether sorting can approach O(n) instead of staying at O(nlogn)  
> **username_0**: Why not take for granted the structure is like an array with typical array methods since it's common computer science to use arrays and we use them everywhere else. Can't you guess even think that I'm using an array? Why do I need to prove that I'm familiar with sorting literature to ask this question? I also thought binary search was the fastest until I saw these algorithms could do O(nloglogn) and my question is if O(nlogloglog...logn) could be possible and then you saynothing is possible which is you lying to me here.  
> **username_5**: @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](http://cstheory.stackexchange.com/faq#etiquette).  
> **username_0**: If I have one comparator circuit per element, why would it not be direct?  
> **username_6**: I am closing this question. As it stands the question is off-topic. Please read the [faq] to  understand the scope of this site, questions like this would probably be more suitable for [cs.se] which has a broader scope.  
> **username_0**: @Kaveh I understand "just checking" would be linear. But checking a solution can be slower than arranging it, don't you think?  
> **username_6**: @Nick, did you read my comment?  
> **username_0**: @Kaveh I even own the book you mentioned ("Intro to algorithms).  
> **username_6**: @Nick, did you read the [faq]?  
> **username_0**: @Kaveh Here's O(nloglogn) http://www.nada.kth.se/~snilsson/software/nloglogn.c  
> **username_6**: @Nick, I have seen that. I still think this is off-topic here. Let me explain why: the target community for this site are professional researchers in theoretical computer science (professors, post-docs, graduate students, and other researchers in research labs, etc.). As such we expect the questions on this site to be relevant to such people. I think your question is off-topic here because of this. The motivation for questions here are normally researching. One can make a research-level question of this, but you haven't stated the question so and you haven't shown that you know the basics.  
> **username_6**: You have seen a post on a site and wanted to see if that is still the best known algorithm and there is nothing wrong with that by itself. However it doesn't really belong here and seems more suitable for [cs.se] which has a more general audience. It could have been an acceptable boarder case question if the question was stated *clearly* and *rigorously* with a reference to the paper but it wasn't. Many of users here also participate on [cs.se] and answer more general level question there, but the scope of this site is more restricted as explained in the [faq].  
> **username_0**: @Kaveh It's not far fetched that O(nloglogn) will develop to O(nlogloglogn) and so on towards linear. The paper even mentions linear sorting. The paper is exactly the background and was the CS site even online when I posted this question to begin with? I didn't know there was a CS site until recently, of course I will thoroughly consider where and what to post. I thought the title of the paper was interesting ("linear sorting") and then you just block that.  

---

## 2 answers

### Answer by username_7 on 2012-06-11. Score: 9 | Accepted answer

(*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](http://www.sciencedirect.com/science/article/pii/S002200009891580X) 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](http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1181890) 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})$.


---

### Answer by username_5 on 2012-06-11. Score: 10

### 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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Stirling%27s_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](http://en.wikipedia.org/wiki/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.


---

