I can see a solution with memory usage : size of( compressed sorted stream ) + size of( compressed sorted chunk ) + size of(compressed stream merge output)
This would work but it means you need to fit your compressed sorted stream in less than a single MB instead of 2MB (and I'm ignoring memory fragmentation problems)
In my solution though when the extra temporary buffer is very small,in the worst case, we need to make sizeof(compressedStream)/sizeof(temporaryBuffer) memmove which can potentially make the algorithm quadratic.
A = Existing compressed sorted chunk; B = Compressed merge output; C = New sorted chunk
Start with:
AAAAAAAAAAAAAAAAAAAAAAAAAAA-----CCCCCC
Merge into B, start at top of A and working your way down:
AAAAAAAAAAAAAAAAAAAAAA-----BBBBBCCCC--
Finish this iteration like:
--------BBBBBBBBBBBBBBBBBBBBBBBB------
Then refill C and sort it:
--------BBBBBBBBBBBBBBBBBBBBBBBBCCCCCC
Merge B back into A, but forwards this time:
AAAAAAAAAA------BBBBBBBBBBBBBBBB---CCC
AAAAAAAAAAAAAAAAAAAAAAAAAAA-----------
I'm not sure your solution work though without memory moving, because in your second step if the values of A are larger than the values of C, the growing B will hit the non decreasing set A.
To convince my self, I wrote for myself the following sequence.
00000224446666666666888888_11133333355555
BytesOfTheCompressedStream_NewSortedChunk________________
BytesOfTheCompressedStream_NewSortedChunk________weNsetyB
OfTheCompressedStream_SortedChunk________________weNsetyB
OfTheCompressedStream_SortedChunk________detroSfOweNsetyB
TheCompressedStream_Chunk________________detroSfOweNsetyB
TheCompressedStream_Chunk_______detroSehTdetroSfOweNsetyB
CompressedStream_Chunk__________detroSehTdetroSfOweNsetyB
Here notice that we hit the existing streams so we need to memmove
CompressedStream_Chunk_esserpmoCdetroSehTdetroSfOweNsetyB
dStream_Chunk__________esserpmoCdetroSehTdetroSfOweNsetyB
dStream_Chunk____knuhCdesserpmoCdetroSehTdetroSfOweNsetyB
Stream_____maertSknuhCdesserpmoCdetroSehTdetroSfOweNsetyB
___________maertSknuhCdesserpmoCdetroSehTdetroSfOweNsetyB
Then reverse it in place and memmove
Then, to get reasonably good time complexity, you use that extra space as a scratch buffer - read in a chunk of input, sort in place (heapsort is good for worst-case time complexity), and merge with the compressed stream. It's not simple to implement, but it does work.