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

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

CC BY-SA 3.0
2012-10-03T20:17:03.907Z
OK, makes perfect sense. Thanks for the reference!
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2012-10-03T03:01:12.877Z
2012-10-03T03:01:12.877Z
Snowie
<p>Does there exist a stable comparison sort using $O(1)$ auxiliary memory and achieving $O(n \log n)$ average run time?</p>

<p>Context: There are comparison sorts with any two of those three desirable characteristics (see <a href="https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms" rel="nofollow">this list</a>). Is there a reason why the three cannot be achieved simultaneously? <em>[Edit: I added the algorithm from the accepted answer to the list on Wikipedia, obviously it wasn't there when I asked the question.]</em></p>

CC BY-SA 3.0
2012-10-02T15:39:55.857Z
See the answer of this question: http://cstheory.stackexchange.com/questions/7248/optimal-sort-algorithm-in-number-of-swaps/7250#7250
Snowie
CC BY-SA 3.0
2012-10-02T18:15:40.903Z
@Snowie "in-place" typically means with space $O(\log n)$, doesn't it?
Raphael
CC BY-SA 3.0
2012-10-02T18:19:36.200Z
@JɛﬀE 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).
Raphael
CC BY-SA 3.0
2012-10-02T18:25:58.520Z
@Snowie: Unless Raphael's objection holds, please post http://www.springerlink.com/content/d7348168624070v7/ as an answer so I can accept it. :)
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2012-10-03T02:09:45.990Z
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.
Tyson Williams
<ds.algorithms><sorting>
Stable comparison sort with $O(1)$ auxiliary memory and $O(n \log n)$ average running time
Antoine Amarilli 'a3nm'
# Stable comparison sort with $O(1)$ auxiliary memory and $O(n \log n)$ average running time

(Asked by: username_0 on 2012-10-02)

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](https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms)). 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.]*

**Tags:** ds.algorithms, sorting

> **Comments:**
> **username_1**: See the answer of this question: http://cstheory.stackexchange.com/questions/7248/optimal-sort-algorithm-in-number-of-swaps/7250#7250  
> **username_2**: @username_1 "in-place" typically means with space $O(\log n)$, doesn't it?  
> **username_2**: @JɛﬀE 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).  
> **username_0**: @username_1: Unless username_2's objection holds, please post http://www.springerlink.com/content/d7348168624070v7/ as an answer so I can accept it. :)  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_1 on 2012-10-03. Score: 8 | Accepted answer

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

> **Comments:**
> **username_0**: OK, makes perfect sense. Thanks for the reference!  

---

