> Is that done by further recursing merges for larger merge sizes? Yes. > Is the number of recursive layers needed to do a big merge determined by the size of

> Is that done by further recursing merges for larger merge sizes? Yes. > 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? Both. I haven't worked out the exact math yet, but it's likely something on the order of O(log (n / s)) recursive layers. > I see that try_merge_into_scratch will fail when the scratch space isn't big enough, which mostly answers my question If you are reading the code, the whole small-memory magic happens in physical_merge: https://github.com/orlp/glidesort/blob/master/src/physical_merges.rs#L31 https://github.com/orlp/glidesort/blob/master/src/physical_m.... Lines 46-59 are the large-enough memory happy path. Lines 60-65 is the low-memory path in-place recursive path. All other merge functions use try_merge_into_scratch as a happy path, and if that fails end up deferring to physical_merge.