3 ms·
i couldn't find a direct reference, but i remembered that sedgewick's c++ algorithms book had an in-place iterative mergesort with no auxiliary space. that prob
by z0r 7y ago
i couldn't find a direct reference, but i remembered that sedgewick's c++ algorithms book had an in-place iterative mergesort with no auxiliary space. that probably was a false memory, but it seems that there is such a beast:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22....
- hinkley 7y agoI remember this article now. As someone else said, for certain time complexities there are more algorithms available. I believe when I realized that fixing my bug would turn it essentially into this algorithm, I found something else to do.
- z0r 7y agoI just tried to read this, and not only is it horrifyingly complex it isn't stable, so it doesn't really fit the bill (even if you allow for strange complexities)
- hinkley 7y agoAha! Thank you. That solves a mystery for me. Skimming it a few minutes ago, I thought it claimed to be stable, and I couldn't figure out why it didn't come to mind when I thought about merge sort. If it's not stable, then what's the point? It's not a merge sort variant by the most important measure, IMO, and as I said, I was only considering merge sort variants. Even with all of the additional logic people have created to avoid worst case performance, quicksort is simpler than this algorithm by a huge margin.