If it's worth saying, but not worth its own post, then it goes here.
Notes for future OT posters:
1. Please add the 'open_thread' tag.
2. Check if there is an active Open Thread before posting a new one. (Immediately before; refresh the list-of-threads page before posting.)
3. Open Threads should start on Monday, and end on Sunday.
4. Unflag the two options "Notify me of new top level comments on this article" and "
I've read some papers (Trabb Pardo, Huang-Langston 1, Huang-Langston 2, Munro-Raman-Salowe, Katajainen-Pasanen 1, Katajainen-Pasanen 2) and there seems to be a "wall" at sqrt(n) extra space. If we have that much space, we can write a reasonable-looking mergesort or quicksort that's stable, in place and O(n log n). But if we have strictly O(1) space, the algorithms become much more complicated, using a sqrt(n) buffer inside the array to encode information about the rest. Breaking through that wall would be very interesting to me.