title: Number of passes in external merge
body: <p>There doesn't seem to be any preexisting questions on this, at least from a title search. I am seeking to find the optimal amount of passes for an external merge. So, if we have 1000 chunks of data, one pass would be a 1000 way merge. Two pass could be 5 groups of 200 chunks, then a final merge of 1 group of 5 chunks. And so on. I've done some math, which must have a flaw, because it looks like two passes never beats one pass. It could very well be a misunderstanding in how data is read, though.</p>
  
  <p>First, a numerical example: </p>
  
  <p>Data: 100 GB<br>
  Ram: 1 GB</p>
  
  <p>Since we have 1GB memory, we can load in 1GB at a time to sort using quicksort or mergesort. Now we have 100 chunks to sort. We can do a 100 way merge. This is done by making <code>RAM/(chunks+1)</code> size buckets = <code>1024MB/101</code> = <code>10.14MB</code>. There are 100 <code>10.14MB</code> buckets for each of the 100 chunks, and one output bucket also of size <code>10.14MB</code>. As we merge, if any input buckets empty, we do a disk seek to refill that bucket. Likewise, when the output bucket gets full, we write to the disk and empty it. I claim that the number of "times the disk needs to read" is <code>(data/ram)*(chunks+1)</code>. I get this from the fact that we have <code>ram/(chunks+1)</code> sized input buckets, and we must read in the entire data for a given pass, so we read <code>(data/bucket_size)</code> times. In other words, every time an input bucket empties we must refill it. We do this over 100 chunks here, so <code>numChunks*(chunk_size/bucket_size)</code> = <code>datasize/bucket_size</code> or <code>100*(1024MB/10.14MB)</code>. BucketSize = <code>ram/(chunks+1)</code> so <code>100*(1024/10.14)</code> =  <code>(data/ram) * (chunks+1)</code> = <code>1024*100MB/1024MB * 101</code> = 10100 reads. </p>
  
  <p>For a two pass system, we do A groups of B #chunks, then a final merge of 1 group of A #chunks. Using previous logic, we have numReads = <code>A*( (data/ram)*(B+1)) + 1*( (data/ram)*(A+1))</code>. We also have <code>A*B</code> = <code>Data/Ram</code>. For instance, 10 groups of 10 chunks, where each chunk is a GB. Here, A = 10 B = 10. 10*10 = 100/1 = 100, which is <code>Data/Ram</code>. This is because <code>Data/Ram</code> was the original number of chunks. For 2 pass, we want to break <code>Data/Ram</code> into A groups of B #chunks. </p>
  
  <p>I'll try to break down the formula here, let D = data, A = #groups, B = #chunks/group, R = RAM</p>
  
  <p><code>A*(D/R)*(B+1) + 1*(D/R)*(A+1)</code> - This is A times the number of reads of an external merge on B #chunks plus the final merge on A #chunks.</p>
  
  <pre><code>A = D/(R*B) =&gt; D^2/(B*R^2) * (B+1) + D/R * (D/(R*B)+1)
  </code></pre>
  
  <p><code>(D^2/R^2)*[1 + 2/B] + D/R</code> is number of reads for a 2 pass external merge. For 1 pass, we have <code>(data/ram)*(chunks+1)</code> where chunks = data/ram for 1 pass. Thus, for one pass we have <code>D^2/R^2 + D/R</code>. We see that a 2 pass only reaches that as the chunk size B goes to infinity, and even then the additional final merge gives us <code>D^2/R^2 + D/R</code>. So there must be something about the reads I'm missing, or my math is flawed. Thanks to anyone who takes the time to help me!</p>