External sort compo?

[yetifoot]

How do you figure out this delicate balance between memory space needed and disk I/O time?

For my program I took Antonis instruction of using only 100Mb of memory. This was because after this 100Mb barrier any memory operations would take place in swap file, therefore being much slower.

So therefore i chose a block size of 96Mb (to allow a little left over room for program variables) I chose the largest block size i could, because memory read/writes are always much faster than disc r/w.

During the merge phase it is not necessary to use memory. I read a record from each block file, compare, and dump the lowest value. The input file that had a record put to output then gets read again, and the cycle continues. I used the memory in the merge phase as purely a file buffer. All the output is put to memory until there is no more room in this buffer, then it is flushed to file. This was to avoid too much seeking on the hard disc.

Would you guys please explain the basics of a QB implementation of how you did the merge passes.

I believe that mac's entry is a QB version using merges, so reading this may help you. I will try and write a pseudo-code version of my code today to explain it better. I did comment my code quite a lot, so even though it is for FB it may still help you.

I get a headache thinking about it

Me too!