How to sort a big file of sentences with variable length?

Question

Suppose I have a file of many lines of string, how to rank the lines of string in lexicographic order?

Details:

• The file size is about 32GBytes;
• Each line can be regarded as one sentence, which contains variable numbers of words separated by spaces, i.e. the length of each line is not fixed;
• Each word contains only ASCII characters;
• I have only 8 GBytes of memory but unlimited disk space;

What I can figure out is an external merge sort, is there any better idea for this specified problem?

Answer 1

The difference between file size and the memory is not that big, therefore I would suggest to split file into more smaller files based on first letter - or if it is not enough, by the first two letters.

Then you can sort each of them with quicksort and save it and when then they are sorted, you can put them back together.

It would be still O(N) I/O operations and O(n*log(N)) CPU operations.

PS : External merge sort is also good way.