How do I sort a file that has a very long list of items?

Question

I have a text file that has a very long list of items. So I want to sort them alphabetically but I do not want to load all the file into the memory (RAM).

I tried loading all the contents of the file to an array and sort them just like I do normally. But the system complains that there are no much memory!!

Thanks, Mohammad

Answer 1

You'll need to read up on external sorting. The basic approach is to use some sort of divide-and-conquer routine like merge sort, where you read and sort a portion of the file, then read and sort another portion of the file, etc. and when you get to the end you merge the sorted portions together.

Answer 2

Maybe the STXXL (Standard Template Library for Extra Large Data Sets) helps.

STXXL offers external sorting amongst others.

Answer 3

You don't have to hold the whole file in memory. If this is a task you don't have to do very often, you can write an application that sorts it very slow. Something like this (pseudo):

vector<int> linesProcessed;
for (int i = 0; i < lineCount; i++)
{
   if (linesProcessed contains i) continue;
   string alphabeticalFirstLine;
   int lineIndex;
   foreach line in oldFile
   {
       if (line is before alphabeticalFirstLine)
       {
            alphabeticalFirstLine = line;
            lineIndex = i;
       }
   }
   write alphabeticalFirstLine to newFile;
   vector.add(lineIndex);
}
clear vector;
delete oldFile;
rename newFile to oldFile;

Answer 4

If you are using some unix-like OS you can use sort command. It will take care about memory consumption. For an example something like "cat large_file | sort" will do the job.

Or you can write your own / use external sorting from the library. Tell us what language are you using and maybe someone will tell you exact library to use.