Algorithm-wise, yeah I can only think of quadratic ones. But if in the question the bottleneck is memory, maybe that's fine? An optimization would be to do selection sort, but in each round select the next group of integers that share the top 32 - ceil(log(2^32 / n)) bits, as that is a cluster in the EF representation, and then sort the lower bits, which can be done in-place in O(k log k) where k is the group size. So if your groups are large enough you get some speedup.
EDIT:
Ah I think that the trick is to always use half of the memory left to read and sort.
- Read 256k integers (1MB), sort in-place, construct EF representation (~500kB)
- Read 128k, sort, and produce another EF (~280kB)
- Keep halving
You do a logarithmic number of rounds, so it's O(n log n). At the end you're left with log(n) EF sets, which fit in less than 2MB (in fact there's some space left, and you could save a few rounds) and you can merge them with a log(n)-way heap into a stream.
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.
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
1. How to even represent 1,000,000,000 sorted integers in only 2 megabytes, which means you can use (slightly more than) 2 bytes per integer. The central observation is that the sum of the deltas is no more than 4294967296. 4294967296 / 1000000 = 4295 which is about 13 bits, so it seems like it should be possible, but it's not easy.
For example, if you use a standard variable length encoding where the highest bit indicates continuation, you would have 7 data bits per byte, but you could have 743,665 times 128 and 256,335 times 16384, which would require 743,665*2 + 256,335*3 = 2,256,335 bytes, which is slightly over 2 megabyte.
If you use the first two bits of the initial byte (so that K bytes encode 8*K - 2 bits). You could have 740,749 times 64 259,251 times 16384, for a total of 259251*3 + 740749*2 = 2,259,251 bytes, slightly worse even.
With 1 continuation bit per nibble the math similarly doesn't work out. So this is starting to look, if not impossible, at least very hard.
2. Imagine that you could represent 1,000,000 sorted integers in 2 megabytes somehow. Then the next problem is to actually create such a sorted sequence from the input.
I think you could make merge sort work if the requirement is "output the elements in sorted order" rather than actually constructing a sorted representation of the array. In that case, you could create sorted sequences of the first 500,000, 250,000, 125,000 etc. elements, and do a 20-way merge in the end, which is O(N log N) overall.This is still somewhat tricky because the average delta of e.g. 500,000 elements can be twice as large as for the overall array, so you might need slightly more space to encode it, so we would need a really efficient compression scheme to make this work.
All in all I'm gravitating towards: this problem isn't generally solvable under the given constraints. With 3 megabytes I think the scheme outlined above works.