3 ms·

One method is to move the compressed output from the top to the bottom of the memory with each cycle: A = Existing compressed sorted chunk; B = Compressed merg

One method is to move the compressed output from the top to the bottom of the memory with each cycle: 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-----------

GistNoesis 5y ago
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. 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

GistNoesis 5y ago

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. 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