CODEWITHSUNDEEP
algorithm
user515974
user515974

Reputation: 51

How to sort n^2 elements in 2n RAM

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.

Upvotes: 5

Views: 544

Answers (2)

jonderry
jonderry

Reputation: 23633

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.

Upvotes: 2

Martin v. Löwis
Martin v. Löwis

Reputation: 127507

It's not possible. You need n^2 memory for the elements alone.

If you don't count this obvious memory consumption, I recommend one of the inplace sort algorithms, such as heapsort. It will take O(1) extra space.

If you are looking for an external sort algorithm where the external storage doesn't count but only the internal one, I recommend to use bottom-up mergesort. You can get this to consume as much or as little internal memory as you want to; to consume approximately 2n memory, always read n/2 elements from each partially-sorted set, and merge them into another array of n elements; then write the result back to disk (preferably into a separate file).

Upvotes: 0

Related Questions