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.
- Insertion sort works, but O(N^2) time complexity is not great with a million elements.
- Quick sort doesn't work since you'd start with an unsorted array which you cannot represent in memory.
- Heap sort doesn't work because it requires random access to the array, which doesn't work with a variable-length encoding.
- Merge sort works in the beginning, but you need temporary space equal to the size of your input, so towards the end you're in trouble.
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.