Counting number of inversions using mergesort in Scala.

Inversions.scala

// I commonly ask / get asked this question in interviews,
// but no candidate has ever used Scala so I thought I'd give it a try.

def inv(list : List[Int]) : Int = doInv(list)._1

def doInv(list : List[Int]) : (Int, List[Int]) =
  if (list.length <= 1) {
    (0, list)
  } else {
    val (left, right) = list.splitAt(list.length / 2)
    val (leftCount, leftList) = doInv(left)
    val (rightCount, rightList) = doInv(right)
    val (mergeCount, mergeList) = doMerge(leftList, rightList)
    (leftCount + rightCount + mergeCount, mergeList)
  }

def doMerge(left : List[Int], right : List[Int], count : Int = 0) : (Int, List[Int]) =                                                                                                                                                                                          
  (left, right) match {
    case (Nil, r) => (count, r)
    case (l, Nil) => (count, l)
    case (lhead :: ltail, rhead :: rtail) =>
      if (lhead <= rhead) {
        val (lcount, list) = doMerge(ltail, right, count)
        (count + lcount, lhead :: list)
      } else {
        val (rcount, list) = doMerge(left, rtail, count)
        (count + left.length + rcount, rhead :: list)
      }   
  }

@rubanm here's my version of it: https://github.com/feliperazeek/scala-playground/blob/master/src/main/scala/algo/CountInversions.scala. still need to improve, ran on a big dataset, ran outta memory.