title: External Sort between two files
body: <p>I'm trying to get my head around an external sort for a requirement I have - and I can't.</p>
  
  <p>The requirement is to externally sort a file of an arbitrary size but using just the original file and one other (call them <code>fileA</code> and <code>fileB</code>) - two files including the original. I can read/write to either of these - so can swap between the two...</p>
  
  <p>I cannot figure out how to implement this - as most sorting algorithms require you to be able to have an overview of the entire array in memory to sort it, surely?</p>
  
  <p>Say I have a random integer array:</p>
  
  <pre><code>[1, 5, 8, 7, 3, 4, 1, 9, 0, 1, 8, 7, 7, 3, 2, 9, 1, 2];
  </code></pre>
  
  <p>And at any given time, I can only read four pages (e.g. four integers) into memory.</p>
  
  <p>On each pass, this gives me five separate arrays to sort:</p>
  
  <pre><code>[1, 5, 8, 7]
  [3, 4, 1, 9] 
  [0, 1, 8, 7] 
  [7, 3, 2, 9]
  [1, 2]
  </code></pre>
  
  <p>If I apply an in-memory sort on these, I then get:</p>
  
  <pre><code>[1, 5, 7, 8]
  [1, 3, 4, 9] 
  [0, 1, 7, 8] 
  [2, 3, 7, 9]
  [1, 2]
  </code></pre>
  
  <p>But if I can only fit four pages into memory at any one time, I don't see how I can further sort these without some horrible complex algorithm which loops over the entire array again and again to ensure its all sorted.</p>
  
  <p>I'm thoroughly confused - because without reading the entire array into memory, we have no idea what elements are before the four pages, or after - so we cannot truly sort them?</p>
  
  <p>Can somebody help me please and explain the crucial step in solving this?</p>