title: Quicksort using Future ends up in a deadlock
body: <p>I have written a quicksort (method <code>quicksortF()</code>) that uses a Scala's Future to let the recursive sorting of the partitions be done concurrently. I also have implemented a regular quicksort (method <code>quicksort()</code>). Unfortunately, the Future version ends up in a deadlock (apparently blocks forever) when the list to sort is greater than about 1000 elements (900 would work). The source is shown below.</p>
  
  <p>I am relatively new to Actors and Futures. What is goind wrong here?</p>
  
  <p>Thanks!</p>
  
  <pre><code>import util.Random
  import actors.Futures._
  
  /**
   * Quicksort with and without using the Future pattern.
   * @author Markus Gumbel
   */
  object FutureQuickSortProblem {
  
    def main(args: Array[String]) {
      val n = 1000 // works for n = 900 but not for 1000 anymore.
  
      // Create a random list of size n:
      val list = (1 to n).map(c =&gt; Random.nextInt(n * 10)).toList
      println(list)
      // Sort it with regular quicksort:
      val sortedList = quicksort(list)
      println(sortedList)
      // ... and with quicksort using Future (which hangs):
      val sortedListF = quicksortF(list)
      println(sortedListF)
    }
  
    // This one works.
    def quicksort(list: List[Int]): List[Int] = {
      if (list.length &lt;= 1) list
      else {
        val pivot = list.head
        val leftList = list.filter(_ &lt; pivot)
        val middleList = list.filter(pivot == _)
        val rightList = list.filter(_ &gt; pivot)
  
        val sortedLeftList = quicksort(leftList)
        val sortedRightList = quicksort(rightList)
        sortedLeftList ::: middleList ::: sortedRightList
      }
    }
  
    // Almost the same as quicksort() except that Future is used.
    // However, this one hangs.
    def quicksortF(list: List[Int]): List[Int] = {
  
      if (list.length &lt;= 1) list
      else {
        val pivot = list.head
        val leftList = list.filter(_ &lt; pivot)
        val middleList = list.filter(pivot == _)
        val rightList = list.filter(_ &gt; pivot)
  
        // Same as quicksort() but here we are using a Future
        // to sort the left and right partitions independently:
        val sortedLeftListFuture = future {
          quicksortF(leftList)
        }
        val sortedRightListFuture = future {
          quicksortF(rightList)
        }
        sortedLeftListFuture() ::: middleList ::: sortedRightListFuture()
      }
    }
  }
  
  class FutureQuickSortProblem // If not defined, Intellij won't find the main method.?!
  </code></pre>