wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Sorting - space constrained
        
(Message started by: DoesNotMatter on Dec 3^rd, 2004, 6:39pm)

Title: Sorting - space constrained
Post by DoesNotMatter on Dec 3^rd, 2004, 6:39pm

Interview Question:-
You have 4 GB of numbers on hard disk and you have 1 GB of RAM on your computer.Give an efficient algorithm to sort these numbers.

Title: Re: Sorting - space constrained
Post by puzzlecracker on Dec 3^rd, 2004, 7:55pm

B+ tree or Heap Sort to do that.... since you don't really need to keep it all in the memory doing so!

Title: Re: Sorting - space constrained
Post by gniv on Feb 3^rd, 2005, 5:22pm

on 12/03/04 at 19:55:57, puzzlecracker wrote:

B+ tree or Heap Sort to do that.... since you don't really need to keep it all in the memory doing so!

Actually, none of these is optimal. The B+-tree repeated insertion is O(N log_B N) I/Os, while the heap is, I think O(N log_2 N).
(B is the disk block size; log_B N is log base B of N)

You can do it in O((N/B) log_B N) as follows:
Load the first GB of the data in memory and sort it. Store it in a file on disk. Load the next GB, sort it, and store it in another file. Do it two more times, until the input is finished.
Then merge the four files by loading one block of each at a time.

The initial sorting steps take O(N/B), and the merging takes O(N/B) as well. The general bound has a log factor, though, because for extremely big inputs many merges may need to be done.