Author |
Topic: Sorting - space constrained (Read 1911 times) |
|
DoesNotMatter
Guest
|
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.
|
|
 IP Logged |
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender: 
Posts: 319
|
 |
Re: Sorting - space constrained
« Reply #1 on: Dec 3rd, 2004, 7:55pm » |
 Quote  Modify
|
B+ tree or Heap Sort to do that.... since you don't really need to keep it all in the memory doing so!
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
gniv
Newbie
Gender:
Posts: 19
|
|
Re: Sorting - space constrained
« Reply #2 on: Feb 3rd, 2005, 5:22pm » |
Quote Modify
|
on Dec 3rd, 2004, 7:55pm, 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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove