Commits

Chema Cortes  committed c57739f

InversionCounter.scala created online with Bitbucket

  • Participants
  • Parent commits 2876245

Comments (0)

Files changed (1)

File InversionCounter.scala

+import scala.annotation.tailrec
+
+package object inversionCounter {
+
+  case class OrderedList[T: Ordering](list: List[T], numInv: BigInt) {
+    def ++(aList: OrderedList[T]) =
+      merge(list, aList.list, Nil, numInv + aList.numInv)
+  }
+
+  object OrderedList {
+    def apply[T: Ordering](list: List[T]) = sort(list)
+  }
+
+  private def sort[T: Ordering](list: List[T]): OrderedList[T] = {
+    val n = list.length
+    if (n == 1)
+      new OrderedList(list, 0) // Base case
+    else {
+      val (left, right) = list.splitAt(n / 2)
+      sort(left) ++ sort(right)
+    }
+  }
+
+  @tailrec
+  private def merge[T: Ordering](left: List[T],
+                                 right: List[T],
+                                 total: List[T],
+                                 numInv: BigInt): OrderedList[T] =
+    (left, right) match {
+      case (Nil, _) => new OrderedList(total ++ right, numInv)
+      case (_, Nil) => new OrderedList(total ++ left, numInv)
+      case (b :: btail, c :: ctail) =>
+        val ord = implicitly[Ordering[T]]
+        if (ord.lteq(b, c))
+          merge(btail, right, total :+ b, numInv)
+        else
+          merge(left, ctail, total :+ c, numInv + left.length)
+    }
+
+}