News for hackers. Stuff that matters.
Re:Sorted Integer Compression by rjmunro on Friday June 18, 2021 @01:36PM (#27552799)
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-----------

Re:Sorted Integer Compression by GistNoesis on Friday June 18, 2021 @02:03PM (#27553076)
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