3 ms·

Thanks. As a follow up, isn't regular quicksort just using O(log N) memory - for the recursion stack? Assuming random pivot and considering average performance.

Thanks. As a follow up, isn't regular quicksort just using O(log N) memory - for the recursion stack? Assuming random pivot and considering average performance. Seems like O(log N) is worth comparing to...?

orlp 5y ago
Glidesort also - from an academic standpoint - always uses O(log N) memory, log2(N)*4 words to be precise. But on 64-bit machines log2(N) is always <= 64, so I just allocate a 64-element array of 4 word structs on the stack. I think it's just much more productive and predictive to say that "glidesort has performance X when using a 512-element buffer" than "glidesort has performance X when using a c log (n) buffer".