External sorting of ints with O(N log N) reads and O(N) writes

Question

I'm interested in algorithm which I should use to meet these requirements (topic subj).

Answer 1

Try this page: Sorting Algorithms. Besides showing nice animations of several algorithms it explains how they work and their complexity.

Answer 2

Check out external merge sort algorithm.

Answer 3

Constantius,

If you're after an algorithm for that type of sorting (where the data can't all fit into core at once), my solution comes from the very earliest days of the "revolution" when top-end machines had less memory than most modern-day calculators.

I haven't worked out the big-O properties but I think it would be O(n) reads, O(n log n) sort phase (depends on the sort method chosen) and O(n) writes.

Let's say your data set has one million elements and you can only fit 100,000 in memory at a time. Here's what I'd do:

• read in the first 100,000, sort them and write that sorted list back out.
• do this for each group of 100,000.
• run a merge operation on the 10 groups.

In other words, once your 10 groups are sorted within the group, grab the first entry from each group.

Then write that the lowest of those 10 (which is the lowest of the whole million) to the output file and read the next one from that group in its place.

Then just continue selecting the lowest of the 10, writing it out and replacing it from the same group. In that way, the final output is the entire sorted list of a million entries.