title: How external merge sort algorithm works?
body: <p>I'm trying to understand how external merge sort algorithm works (I saw some answers for same question, but didn't find what I need). I'm reading the book "Analysis Of Algorithms" by Jeffrey McConnell and I'm trying to implement the algorithm described there.</p>
  
  <p>For example, I have input data: <code>3,5,1,2,4,6,9,8,7</code>, and I can load only 4 numbers into memory.</p>
  
  <p>My first step is read the input file in 4-number chunks, sort them in memory and write one to file A and next to file B.</p>
  
  <p>I got:  </p>
  
  <pre><code>A:[1,2,3,5][7]  
  B:[4,6,8,9]
  </code></pre>
  
  <p>Now my question how can I merge chunks from these files to the bigger ones if they will not fit to the memory? Jeffrey McConnell wrote that I need to read half chunks and merge them to next files C and D.</p>
  
  <p>But I got wrong sequence:</p>
  
  <pre><code>C:[1,2,4,6,3,8,5,9]
  D:[7]
  </code></pre>
  
  <p>Can anyone provide an example with step by step instruction, please?</p>
  
  <p>PS: I understand how to merge number by number by reading from file, but how do I do it with in-memory buffers to reduce I/O operations?</p>