A Sorting Sort of Problem (1)
(Freudenthal, as inspired by Bentley):

Consider a file containing one billion distinct 32-bit integers. Your task is to write a new file that contains this set in sorted order. Your computer has two gigabytes of memory (RAM) available and more than enough available disk space for any algorithm you choose.

Assume that

• reading or writing a datum sequentially to a file takes much longer (say 100x) longer than memory access.
• that we can't jump-around files efficiently (they must be accesed sequentially from the beginning)

What's the fastest way to do this?

Advanced question: what is the smallest amount of memory you use to solve this problem without significantly increasing execution time?