> How can it do merges in space (much) smaller than the input.
That's part of it. More specifically I'm interested in the dynamic nature of the space overhead. In the video you linked, from 10 to 12 seconds, it looks like the algorithm is using about n/4 scratch space. But for larger arrays, it's bounded at n/8. Is that done by further recursing merges for larger merge sizes? Is the number of recursive layers needed to do a big merge determined by the size of the input, or the size of the scratch space?
I see that try_merge_into_scratch will fail when the scratch space isn't big enough, which mostly answers my question https://github.com/orlp/glidesort/blob/master/src/physical_m.... But I'm still not sure how that failure causes the overall algorithm to change
(I have been trying to ask about how glidesort uses the preallocated scratch space internally, not how it interfaces with system memory and system allocators.)
That's part of it. More specifically I'm interested in the dynamic nature of the space overhead. In the video you linked, from 10 to 12 seconds, it looks like the algorithm is using about n/4 scratch space. But for larger arrays, it's bounded at n/8. Is that done by further recursing merges for larger merge sizes? Is the number of recursive layers needed to do a big merge determined by the size of the input, or the size of the scratch space?
I see that try_merge_into_scratch will fail when the scratch space isn't big enough, which mostly answers my question https://github.com/orlp/glidesort/blob/master/src/physical_m.... But I'm still not sure how that failure causes the overall algorithm to change
(I have been trying to ask about how glidesort uses the preallocated scratch space internally, not how it interfaces with system memory and system allocators.)