# Is integer sorting possible in O(n) in the transdichotomous model?

To my knowledge there doesn't exist a $O(n)$ worst-case algorithm that solves the following problem:

Given a sequence of length $n$ consisting of finite integers, find the permutation where every element is less than or equal to its successor.

But is there a proof that it doesn't exist, in the transdichotomous model of computation?

Note that I'm not limiting the range of the integers. I'm not limiting solutions to comparison sorts either.

• As far I as I know, there might be an $O(n)$ time algorithm for SAT! So the answer is no.
– Simd
Apr 11, 2015 at 16:02
• AFAIK, this is still an open problem.
– Juho
Apr 11, 2015 at 16:20
• I don't know whether there can be a meaningful answer until you specify what model of computation you are using, given that you are not limiting your computer to comparisons and swaps. With only RAM and two-number comparisons, an argument from entropy gives a $\Omega(n\cdot log(n))$ time bound, even for transdichotomous computers. Trivially, if instead of swaps and comparisons, sorting is an elementary operation, it can be done in $\Theta(1)$. If inserting an integer in the right place is an elementary operation, $\Theta(n)$. Did you have a specific beyond-comparison-swap model in mind? Oct 18, 2015 at 19:52
• @LieuweVinkhuijzen My question specifies the transdichotomous model of computation. In plain English: a model of computation where the word size of the machine is large enough to hold any integer of the problem. So comparing any two integers is O(1), but so is adding, multiplying, etc them. In this model of computation the entropic bound has already been beaten, see Han, Yijie (2004), "Deterministic sorting in O(n log log n) time and linear space".
– orlp
Oct 18, 2015 at 21:27
• @orlp I see; if you take advantage of the structure of the integers, you can beat the entropic bound. I didn't know about integer sorting; I'll be sure to read up on that topic! Oct 18, 2015 at 22:17

## 2 Answers

Integers can be stably sorted in $O(n)$ time with $O(1)$ additional space. More precisely, if you have $n$ integers in the range $[1, n^c]$, the can be sorted in O(n) time.

This was only shown a couple of years ago by a team including the late Mihai Pătrașcu (which should surprise nobody who is familiar with his work). It's a remarkable result which I'm surprised more people don't know about, because it means that the problem of sorting integers is (theoretically) solved.

There is a practical algorithm (given in the paper above) if you're allowed to modify keys. Basically, you can compress sorted integers more than you can compress unsorted integers, and the extra space that you gain is precisely equal to the extra memory needed to do the radix sort. They also give an impractical algorithm which supports read-only keys.

• From what I can understand from the abstract this is not general - it can only sort words up to $\log n$ in size in $O(n)$. My question explicitly mentions unbounded integers.
– orlp
Jan 27, 2016 at 23:45
• @orlp The third algorithm in the paper talks about unbounded-length integers. Jan 28, 2016 at 2:51
• Perhaps I'm misreading it, but I can only see a description of a method to reduce the memory usage of unbounded integer sorting algorithms. Quoting from the abstract (emphasis mine): "Another interesting question is the case of arbitrary $c$. Here we present a black-box transformation from any RAM sorting algorithm to a sorting algorithm which uses only O(1) extra space and has the same running time."
– orlp
Jan 28, 2016 at 4:03
• Forgive me, but in it's current state this answer doesn't answer the question at all. I explicitly mentioned that the integers are not bounded. This answer solves an entirely different problem.
– orlp
Jan 29, 2016 at 12:48
• The final point is now no longer in a small font :)
– orlp
Jan 29, 2016 at 23:35

For integers, you can use the Radix sort. It creates buckets and then sorts a list of numbers in $O(bn)$ where $b$ is an upper bound on the size in bits of any integer, and $n$ the number of elements to sort.

If there is no upper bound on the size of your integers, then I don't believe there is any known linear-time sorting algorithm.

• Welcome! What you say is completely true but I don't think it answers the question. The question asks specifically for a proof that the required algorithm does not exist in a particular model of computation; merely saying that no such algorithm is known doesn't prove that none exists. Jan 28, 2016 at 1:02
• Actually, b being a constant in our problem, I consider this algorithm being in o(n) Jan 28, 2016 at 8:22
• The question says nothing about $b$ being a constant. It just says that we have $n$ numbers. Those numbers could be arbitrarily large. (Also, it's probably just a typo in your comment but note that $O(n)$ and $o(n)$ are two very different things.) Jan 28, 2016 at 8:42
• Yes, definitely a typo ;) in his question, as you suppose a number fitting in a word of length b, it becomes a constant. Jan 28, 2016 at 8:49
• That's not making word length a constant. ​ (Otherwise, there would be no reason to explicitly assume "that operations on single words take constant time per operation". ​ ​ ​ ​
– user12859
Jan 30, 2016 at 1:32