title: Finding k-largest elements of a very large file (while k is very LARGE)
body: <p>Let's assume that we have a very large file which contains billions of integers , and we want to find <code>k</code> largest elements of these values , </p>
  
  <p>the tricky part is that <code>k</code> itself is very large too , which means we cannot keep <code>k</code> elements in the memory (for example we have a file with 100 billon elements and we want to find 10 billion largest elements)</p>
  
  <p>How can we do this in <code>O(n)</code> ?</p>
  
  <p>What I thought : </p>
  
  <p>We start reading the file and we check it with another file which keeps the <code>k</code> largest elements (sorted in increasing order) , if the read element is larger than the first line of the second file we delete the first line and we insert it into the second file , the time complexity would be of <code>O(NlogK)</code> (if we have random access to that file , otherwise it would be 'O(Nk)'</p>
  
  <p>Any idea to do this in <code>O(n)</code> , I guess if we have external version of <code>Selection algorithm</code> (the partitioning algorithm in quicksort) we would be able to do this in <code>O(n)</code> but I couldn't find it anywhere</p>