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