<p>Mergesort satisfies all three requirements (when merging is performed in place).
See Pardo, L.T., "Stable  sorting  and  merging  with  optimal  space  and  time 
bounds", SIAM J. Comput. 6 (1977), 351-372.</p>

CC BY-SA 3.0
2012-04-11T11:54:37.287Z
I think that the algorithm uses $O(1)$ pointers, but has a recursive call stack that is logarithmic in the size of the list. Am I mistaken?
aelguindy
CC BY-SA 3.0
2012-04-11T12:15:49.323Z
Mergesort can be implemented without recursion, essentially by doing a bottom-up level-order traversal of the recursion tree.
Jeffε
CC BY-SA 3.0
2012-04-13T15:34:05.117Z
there is a nice paper by Salowe and Steiger that describes some background and gives simplified algorithms: http://dx.doi.org/10.1016/0196-6774(87)90050-2
Sasho Nikolov
CC BY-SA 3.0
2014-06-27T13:53:04.693Z
Here is an implementation of such a sort, along with a lot of documentation of how it's implemented: https://github.com/BonzaiThePenguin/WikiSort/tree/master
R.. GitHub STOP HELPING ICE
CC BY-SA 3.0
2012-04-11T11:47:41.583Z
2012-04-11T11:47:41.583Z
david
<p>For a comparison based sorting algorithm, it is desirable to:</p>

<ol>
<li>Be stable</li>
<li>Run in $O(n\ \log n)$</li>
<li>Operate in $O(1)$ space</li>
</ol>

<p>I can find algorithms that satisfy any two of these but I can't find any that satisfy all three. Does it exist? Is it proven not to exist?</p>

<ds.algorithms><sorting>
Optimal comparison-based stable sorting in constant space
aelguindy
# Optimal comparison-based stable sorting in constant space

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

For a comparison based sorting algorithm, it is desirable to:

1. Be stable
2. Run in $O(n\ \log n)$
3. Operate in $O(1)$ space

I can find algorithms that satisfy any two of these but I can't find any that satisfy all three. Does it exist? Is it proven not to exist?

**Tags:** ds.algorithms, sorting

---

## 1 answers

### Answer by username_1 on 2012-04-11. Score: 14 | Accepted answer

Mergesort satisfies all three requirements (when merging is performed in place).
See Pardo, L.T., "Stable sorting and merging with optimal space and time
bounds", SIAM J. Comput. 6 (1977), 351-372.

> **Comments:**
> **username_0**: I think that the algorithm uses $O(1)$ pointers, but has a recursive call stack that is logarithmic in the size of the list. Am I mistaken?  
> **username_2**: Mergesort can be implemented without recursion, essentially by doing a bottom-up level-order traversal of the recursion tree.  
> **username_3**: there is a nice paper by Salowe and Steiger that describes some background and gives simplified algorithms: http://dx.doi.org/10.1016/0196-6774(87)90050-2  
> **username_4**: Here is an implementation of such a sort, along with a lot of documentation of how it's implemented: https://github.com/BonzaiThePenguin/WikiSort/tree/master  

---

