Thanks, I got it. The main trick is the standard "interview" trick of writing from right to left.
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.
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