How to sort n^2 elements in 2n RAM

Question

Can somebody please tell me how to sort n^2 elements using 2n amount of RAM. One possible approach is to divide into n arrays of size n each. And then do a merge sort within the n elements and then finally keep a size n heap on the n arrays. However, this would mean that every time one element gets placed, I do a disk read, and every time n elements complete, I do a disk write. Any better suggestions? Thanks.

Answer 1

If you happen to have a cache-oblivious priority queue implementation lying around, you can use it to achieve an optimal running time in terms of memory transfers at each level in the disk and memory hierarchy (See http://courses.csail.mit.edu/6.897/spring05/lec/lec23.pdf).

Otherwise, if you just want to write simple code from scratch, a disk-based implementation of mergesort should work well. Basically, you can sort a range of the array by first recursively sorting the "left" and "right" halves, and then merging them using the 2n memory to buffer the recursively sorted sub-arrays from disk. For a simple implementation, this is not in place, so you will have to keep two copies of the array on disk and shuttle back and forth.