If you have a memory that has less than 1 million integers, you have to sort through co-sequential process (File Structures in C++, Folk), that use heapsort too, and list the first 1 million integers from the sorted file. With this method you can have only 64bytes of Ram (or less, depending of your file register size) to sort a 1Tb file.
On Wed, Jun 23, 2010 at 4:06 PM, Dave <[email protected]> wrote: > Form the first million numbers into a max-heap, where the largest > number at the root. Any number in the input file that is larger than > the root can be ignored. If it is smaller than the root, replace the > root with the number and trickle it down the heap to restore the heap > condition. Worst case is if the file is in descending order, in which > case, there are about 2 * 0.999999 trillion * log_2(1 million) data > comparisons. > > Dave > > On Jun 23, 7:18 am, amit <[email protected]> wrote: >> Given a set of 1 Trillion integers on hard disk, find the smallest 1 >> million of them. You can fit at most 1 million integers in memory at a >> time. State the fastest solution you can think of. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
