title: Time Complexity/Cost of External Merge Sort
body: <p>I got this from a <a href="http://www-inst.eecs.berkeley.edu/~cs186/sp03/section/mreview2.pdf" rel="noreferrer">link</a> which talks about external merge sort.</p>
  
  <p>From slide 6 Example: with 5 buffer pages, to sort 108 page file</p>
  
  <ul>
  <li><p>Pass0: [108/5] = 22 sorted runs of 5 pages each (last run only with 3 pages)</p></li>
  <li><p>Pass1 [22/4] = 6 sorted runs of 20 pages each (last run only with 8 pages)</p></li>
  <li><p>Pass2: [6/3] = 2 sorted runs, 80 pages and 28 pages</p></li>
  <li><p>Pass 3: [2/2] = 1 Sorted file of 108 pages</p></li>
  </ul>
  
  <p>Question: My understanding is in external merge sort, in pass 0 you create chunks and then sort each chunk. In remaining passes you keep merging them.
  So, applying that to the above example, since we have only 5 buffer pages, in Pass 0 its clear we need 22 sorted runs of 5 pages each.</p>
  
  <ol>
  <li><p>Now, why are we doing sorted runs for remaining passes instead or merging ? </p></li>
  <li><p>How come it tells for pass 1, 6 sorted runs of 20 pages each when we have only 5 buffer pages ?</p></li>
  <li><p>Where exactly is merge happening here ? and how is N reducing in each pass i.e from 108 to 22 to 6 to 2 ?</p></li>
  </ol>