[twouhm]

So what is the trick?

[_wmd]

It's the opening problem from Programming Pearls: http://www.fusu.us/2013/06/bitmap-sort.html

(edit: better link)

[sirclueless]

How is this relevant? A bitmap of size 2^32 is 512MB in size and you only have 2MB of memory.

[lalaland1125]

The trick is that you only need to store the unordered list of seen integers as your state while you sort. This takes about 1.5MB or so. The reduction in space comes from the fact that you don't have to store the order (for example, you could store the numbers sorted and only record offsets. That saves space because the offsets will be smaller)