2
$\begingroup$

Does there exist a stable comparison sort using $O(1)$ auxiliary memory and achieving $O(n \log n)$ average run time?

Context: There are comparison sorts with any two of those three desirable characteristics (see this list). Is there a reason why the three cannot be achieved simultaneously? [Edit: I added the algorithm from the accepted answer to the list on Wikipedia, obviously it wasn't there when I asked the question.]

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ See the answer of this question: cstheory.stackexchange.com/questions/7248/… $\endgroup$
    – Snowie
    Oct 2, 2012 at 15:39
  • 1
    $\begingroup$ @Snowie "in-place" typically means with space $O(\log n)$, doesn't it? $\endgroup$
    – Raphael
    Oct 2, 2012 at 18:15
  • 1
    $\begingroup$ @JɛffE I don't think that is true for most (in-place) versions of Quicksort, e.g. Sedgewick's: you inadvertantly change the order of duplicates. You would have to break the tie when directly comparing the two elements (which happens iff one is selected as pivot, i.e. later if at all) but by then positions are skrewed (unless you want to store the original indices; that would cost $O(n)$ memory). $\endgroup$
    – Raphael
    Oct 2, 2012 at 18:19
  • $\begingroup$ @Snowie: Unless Raphael's objection holds, please post springerlink.com/content/d7348168624070v7 as an answer so I can accept it. :) $\endgroup$
    – a3nm
    Oct 2, 2012 at 18:25
  • 1
    $\begingroup$ I agree with Rapheal. "In-place" means that there is only a constant number of addition locations to store elements, but each element requires $O(\log n)$ bits to describe. $\endgroup$
    – Tyson Williams
    Oct 3, 2012 at 2:09

1 Answer 1

Reset to default
8
$\begingroup$

There is a sort algorithm with $O(1)$ auxiliary words and achieving $O(n\log n)$ worst-case run time, where $n$ is the length of the input array. http://www.springerlink.com/content/d7348168624070v7/

I don't think that the question seeks an algorithm with $O(1)$ auxiliary bits, because such algorithm must be tricky. I mean, if we cannot use even $O(\log n)$ bits, then we cannot use a simple for-loop (for(i=0, i < n, i++) {...} ) in the algorithm without introducing variable i (which require additional $O(\log n)$ bits).

Improve this answer
$\endgroup$
1
  • $\begingroup$ OK, makes perfect sense. Thanks for the reference! $\endgroup$
    – a3nm
    Oct 3, 2012 at 20:17

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.