4 ms·
> 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 b
by orlp 5y ago
> 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.
- omegalulw 5y agoThanks. 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 agoGlidesort 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".