Inversionen zählen.

inversionen.scala

object mergesort {

  def mergesort(a: List[Int], b: List[Int]): List[Int] = (a, b) match {
    case (Nil, Nil) => Nil
    case (xs, Nil) => xs
    case (Nil, ys) => ys
    case (x :: xs, y :: ys) => if (x < y) x :: mergesort(xs, b) else y :: mergesort(a, ys)
  }                                               //> mergesort: (a: List[Int], b: List[Int])List[Int]

  def sort(a: List[Int]): List[Int] = a match {
    case Nil => Nil
    case x :: Nil => a
    case x :: xs => {
      val (b: List[Int], c: List[Int]) = a.splitAt(math.round(a.length / 2))
      mergesort(sort(b), sort(c))
    }
  }                                               //> sort: (a: List[Int])List[Int]

  def mergesort_inv(a: List[Int], b: List[Int]): (List[Int], Int) = (a, b) match {
    case (Nil, Nil) => (Nil, 0)
    case (xs, Nil) => (xs, 0)
    case (Nil, ys) => (ys, 0)
    case (x :: xs, y :: ys) => {
    	if (x < y) {
    		val (next: List[Int], next_inv: Int) = mergesort_inv(xs, b)
    		(x :: next, next_inv)
    	} else {
    		val (next: List[Int], next_inv: Int) = mergesort_inv(a, ys)
    		(y :: next, a.length + next_inv)
    	}
    }
  }                                               //> mergesort_inv: (a: List[Int], b: List[Int])(List[Int], Int)

  def count(a: List[Int]): (List[Int], Int) = a match {
    case Nil => (a, 0)
    case x :: Nil => (a, 0)
    case x :: xs => {
      val (b: List[Int], c: List[Int]) = a.splitAt(math.round(a.length / 2))
    	val (next_b: List[Int], count_b: Int) = count(b)
    	val (next_c: List[Int], count_c: Int) = count(c)
    	val (next_merge: List[Int], count_merge: Int) = mergesort_inv(next_b, next_c)
    	(next_merge, count_b + count_c + count_merge)
    }
  }                                               //> count: (a: List[Int])(List[Int], Int)

  mergesort_inv(List(4, 5, 6), List(1, 2, 3))     //> res0: (List[Int], Int) = (List(1, 2, 3, 4, 5, 6),9)
  mergesort_inv(List(4, 5, 6), List(1, 2))        //> res1: (List[Int], Int) = (List(1, 2, 4, 5, 6),6)
  count(List(7,1,2,4,3,8,5,10,9,6))               //> res2: (List[Int], Int) = (List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10),12)
  count(List(4,5,6,1,2,3))                        //> res3: (List[Int], Int) = (List(1, 2, 3, 4, 5, 6),9)
  count(List(6,5,4,3,2,1))                        //> res4: (List[Int], Int) = (List(1, 2, 3, 4, 5, 6),15)
  count(List(1,2,8,4,5,7,3))                      //> res5: (List[Int], Int) = (List(1, 2, 3, 4, 5, 7, 8),7)
}