9
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ As far I as I know, there might be an $O(n)$ time algorithm for SAT! So the answer is no. $\endgroup$
    – felipa
    Apr 11 '15 at 16:02
  • 5
    $\begingroup$ AFAIK, this is still an open problem. $\endgroup$
    – Juho
    Apr 11 '15 at 16:20
  • 2
    $\begingroup$ 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? $\endgroup$
    – Lieuwe Vinkhuijzen
    Oct 18 '15 at 19:52
  • 2
    $\begingroup$ @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". $\endgroup$
    – orlp
    Oct 18 '15 at 21:27
  • $\begingroup$ @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! $\endgroup$
    – Lieuwe Vinkhuijzen
    Oct 18 '15 at 22:17
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – orlp
    Jan 27 '16 at 23:45
  • $\begingroup$ @orlp The third algorithm in the paper talks about unbounded-length integers. $\endgroup$
    – Pseudonym
    Jan 28 '16 at 2:51
  • 1
    $\begingroup$ 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." $\endgroup$
    – orlp
    Jan 28 '16 at 4:03
  • 3
    $\begingroup$ 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. $\endgroup$
    – orlp
    Jan 29 '16 at 12:48
  • 1
    $\begingroup$ The final point is now no longer in a small font :) $\endgroup$
    – orlp
    Jan 29 '16 at 23:35
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 5
    $\begingroup$ 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. $\endgroup$
    – David Richerby
    Jan 28 '16 at 1:02
  • $\begingroup$ Actually, b being a constant in our problem, I consider this algorithm being in o(n) $\endgroup$
    – RFC 2549
    Jan 28 '16 at 8:22
  • 2
    $\begingroup$ 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.) $\endgroup$
    – David Richerby
    Jan 28 '16 at 8:42
  • $\begingroup$ Yes, definitely a typo ;) in his question, as you suppose a number fitting in a word of length b, it becomes a constant. $\endgroup$
    – RFC 2549
    Jan 28 '16 at 8:49
  • 1
    $\begingroup$ 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". ​ ​ ​ ​ $\endgroup$
    – user12859
    Jan 30 '16 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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