ParMergeSort.scala

  def parMergeSort(l:List[Int]):Future[List[Int]] = {

    def merge(elements: List[Int]): Future[List[Int]] = {
      elements match {
        case ll if ll.size <= 1 ⇒ Future.successful(elements)
        case ll ⇒
          val middle = ll.size / 2
          val (left, right) = ll.splitAt(middle)

          val mLeft = Future(merge(left))
          val mRight = Future(merge(right))

          for {
            l ← mLeft.flatMap(identity)
            r ← mRight.flatMap(identity)
            merge ← Future(mergeHalves(l, r))
          } yield merge

      }
    }

    def mergeHalves(l: List[Int], r: List[Int]): List[Int] = {

      (l, r) match {
        case (Nil, right) ⇒ right
        case (left, Nil) ⇒ left
        case (left :: ll, right :: rr) =>
          if (left < right)
            left :: mergeHalves(ll, r)
          else
            right :: mergeHalves(l, rr)
      }

    }

    merge(l)
  }