Hacker News Reader

> Is the buffer here extra memory in addition to the input?

Yes.

> What about just an O(log N) size buffer?

That would effectively just be a constant sized buffer. Honestly O(log N) factors where N is the size of the input are overrated and are probably best seen as a constant factor. Like, even if you're sorting 16 gigabytes of 32-bit floats, log2 N is still just 32.

View on HN

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

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

Reply on news.ycombinator.com