Considering you are in the linux/unix section.
The *nix sort command makes use of an external merge sorting algorithm. What it means is, that it will use less memory than is available regardless of the size the file might be that is being sorted. This has not been properly documented in wikipedia but here are some articles.
Use a memory mapped file, you will "get" a contiguous piece of memory, sort that, operating system will take care of readingwriting to the file without loading whole file in memory. In *nix I think you need to use mmap() for this. (windows supports this too, but has differnt APIs)
first divide it into small parts(like 1000 :D )
then just start sorting each of them.
now select two small file, load the first of both.
call the smaller one tmp(or anything else)
now write tmp to answer file
now read next line from file who had tmp, and repeat until you reach EOF.