title: Top n items in a List ( including duplicates )
body: <p>Trying to find an efficient way to obtain the top N items in a very large list, possibly containing duplicates.</p>
  
  <p>I first tried sorting &amp; slicing, which works. But this seems unnnecessary. You shouldn't need to sort a very large list if you just want the top 20 members.
  So I wrote a recursive routine which builds the top-n list. This also works, but is very much slower than the non-recursive one! </p>
  
  <p>Question: Which is my second routine (elite2) so much slower than elite, and how do I make it faster ? My code is attached below. Thanks.</p>
  
  <pre><code>import scala.collection.SeqView
  import scala.math.min
  object X {
  
      def  elite(s: SeqView[Int, List[Int]], k:Int):List[Int] = {
          s.sorted.reverse.force.slice(0,min(k,s.size))
      }
  
      def elite2(s: SeqView[Int, List[Int]], k:Int, s2:List[Int]=Nil):List[Int] = {
          if( k == 0 || s.size == 0) s2.reverse
          else {
              val m = s.max
              val parts = s.force.partition(_==m)
              val whole = if( parts._1.size &gt; 1) parts._1.tail:::parts._2 else parts._2
              elite2( whole.view, k-1, m::s2 )
          }
      }
  
      def main(args:Array[String]) = {
          val N = 1000000/3
          val x = List(N to 1 by -1).flatten.map(x=&gt;List(x,x,x)).flatten.view
          println(elite2(x,20))
          println(elite(x,20))
      }
  }
  </code></pre>