Theorytically We can use External memory merge sort procedure. But
phase II (merging) of this procedure seems to be problematic.
I agree.
If you are facing low disk space you can define some container type
whose elements stored on disk (file) locations rather than ram, then
use standard algorithms (e.g. std::sort) ,but this looks too slow
and I am worried about too many times of writing to disk.
Break the file into big "chunks"
This is good: If your using 32-bit ints then we are dealing with the
range [0,4G-1] of integers you can divide this range into a few (say
8) files each one catching numbers in its own range (say [0,512M-1] ,
[512M,1G-1] ... [3.5G,4G-1] respectively ) then delete/archive the
original file and merge the above files into one.I do not see too much
problem in merging any more.