TADM2E 4.43

From Algorithm Wiki
Jump to: navigation, search

Sort the first 2MB of it, and save to disk. Continue doing so until it is all sorted into sub arrays. Then use merge sort to combine sub arrays, only loading necessary data into memory.

The n-way merge sort can itself be done with a heap. Maintain 250 (=500/2) pointers, add the elements pointed to to a heap, pop the minimum and increment the pointer.