4 ms·
Is the buffer here extra memory in addition to the input? What about just an O(log N) size buffer?
by omegalulw 5y ago
Is the buffer here extra memory in addition to the input? What about just an O(log N) size buffer?
- 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".