title: merge k lists with o(nlogk)
body: <p>Is the running time of the <code>Merge</code> algorithm O(<em>n</em> log <em>k</em>)?</p>
  
  <ul>
  <li><em>k</em> is the number of lists.</li>
  <li><em>n</em> is the total number of elements in all of the lists (<em>n</em> = <em>n</em><sub>1</sub> + <em>n</em><sub>2</sub> + ... + <em>n</em><sub><em>k</em></sub>).</li>
  </ul>
  
  <hr>
  
  <pre><code>algorithm MakingAHalf(List_Of_Lists)
      if List_Of_Lists.size() = 1
          return the only list in List_Of_Lists
      else
          split List_Of_Lists into two halfs (First_Half and Second_Half)
      MakingAHalf(First_Half)
      MakingAHalf(Second_Half)
      Merge(First_Half, Second_Half, Min_Heap)
  </code></pre>
  
  <hr>
  
  <pre><code>algorithm Merge(First_Half, Second_Half, Min_Heap)   //T(n) = O(n log k)?
      while First_Half  is not empty and First_Second is not empty do
          if First_Half.first().element() &lt; Second_Half.first().element() then
              Insert(Min_Heap, First_Half.remove(First_Half.first()))
          else
              Insert(Min_Heap, Second_Half.remove(Second_Half.first())  
      while First_Half is not empty do
          Insert(Min_Heap, First_Half.remove(First_Half.first()) 
      while Second_Half is not empty do
          Insert(Min_Heap, Second_Half.remove(Second_Half.first())
  </code></pre>
  
  <hr>
  
  <pre><code>algorithm Insert(A, key)
      A[n+1] &lt;-- key
      while (i &gt; 1) and (A[i] &gt; A[[i/2]]) do
          swap A[i] and A[[i/2]]
          i &lt;-- i - 1
  </code></pre>