Your approach is great if a full sort was required. But what I was trying to say in my earlier post above is that the OP does not actually require a full sort, because there are about 900 sort keys for 5 million records. So that simply splitting the data into 900 buckets (files) and then reread the files in the right order is all what is needed. In short, each piece of data is read and written twice and compared only once. This is basically an O(n) algorithm and will be much faster than any general purpose sorting algorithm.