4
$\begingroup$

I need some help with this question from my problem set. I do not want a solution but some $\textbf{hints}$ on how to proceed.

Given $n$ records in a file that are so numerous, that just storing the $n$ keys alone would require more RAM than is available on your computer. Let $m$ be the maximum number of records that you can store in RAM at once. Assuming that $m >$ $\sqrt{n}$, produce a $\mathcal{O}(n \log n)$ time algorithm for sorting the $n$ records. The sorted records would then be written to a file, since it will not be possible for them to all fit in memory at once.

$\textbf{My approach:}$ I figure I should use a heap based approach. Try to create a type of online algorithm to read $m$ records at a time, and then use heapsort or a type of comparison based algorithm to solve it?

$\textbf{Related Questions:}$

1) I don't understand the underlying assumption of letting $m>\sqrt{n}$?

$\endgroup$
4
$\begingroup$

Hint: Convert the input into $n/m < m$ chunks of length $m$ and sort the chunks. Then use your heap idea. Note that you're using the assumption $m > \sqrt{n}$ so that the heap fits in memory.

$\endgroup$
  • $\begingroup$ Wow! prefect hint! Gave me sufficient information to proceed while leaving me with enough for me to figure out myself. $\endgroup$ – user119264 Mar 28 '16 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.