15:46:07beachPractical In-place Mergesort, by Katajainen, Pasanen, and Teuhola.
15:46:33jcowanCiteseer ftw, even if the PDF is backwards
15:48:01beachThat is one of the SICL projects I would like to subcontract, in fact. I would like to see an intermediate between an ordinary merge sort and one of the O(1) space algorithms suggested. One could use the stack as additional space if there is enough stack space. Certainly, for the base case of only a few dozen elements.
16:02:54jcowanhttps://www.sciencedirect.com/science/article/pii/S1877050910005478 is a more canonical URL
16:03:29beachshka_: Looks interesting. I would want the taker of the challenge to implement several algorithms and compare them, of course. And perhaps even combine them in interesting ways, depending on the situation.
16:04:47shka_beach: i will take a shot at the algorithm i pasted on weekend