As others have mentioned, you need 7 bits per number (on average) if you store the numbers as deltas in sorted form. So 7M bits out of 8388608 bits yields 1.32MB of working set.
One could implement a simple block allocator, where each block contains a sequential list of deltas.
The trick to fast insertion is to place new blocks at addresses interpolated between 0 and 10^8. If there is a collision, merge blocks. If the input distribution is off, physically reallocate colliding blocks left or right into free space.
So inserting the numbers 10, 20, 1000, 2000, 1M, 2M would give you a heap looking like:
One could implement a simple block allocator, where each block contains a sequential list of deltas.
The trick to fast insertion is to place new blocks at addresses interpolated between 0 and 10^8. If there is a collision, merge blocks. If the input distribution is off, physically reallocate colliding blocks left or right into free space.
So inserting the numbers 10, 20, 1000, 2000, 1M, 2M would give you a heap looking like:
[head->[10,10]->[980]->[1000]->[998000]->[1000000]->tail]
As more numbers are inserted, blocks combine until you end up with one contiguous block.