import io.Source
 
object MSort {
  def main(args:Array[String]) {
    val fileWithNumbers = "/Users/tmorrow/Documents/IntegerArray.txt"
    val inversions: BigInt = numberOfInversions(Source.fromFile(new java.io.File(fileWithNumbers)).getLines().map(Integer.parseInt).toList)
    println(inversions)
  }
 
  def numberOfInversions(collection: List[Int]): BigInt = {
    var count: BigInt = 0
    def inversionsInner(innerCollection: List[Int]): List[Int] = {
      def merge(left: List[Int], right: List[Int]): Stream[Int] = (left, right) match {
        case (x :: xs, y :: ys) if x < y=> { Stream.cons(x, merge(xs, right)) }
        case (x :: xs, y :: ys) => { count = count + left.length; Stream.cons(y, merge(left, ys)) }
        case _ => if (left.isEmpty) right.toStream else left.toStream
      }
      val n = innerCollection.length / 2
      if (n == 0) innerCollection
      else {
        val (lowerHalf, upperHalf) = innerCollection splitAt n
        merge(inversionsInner(lowerHalf), inversionsInner(upperHalf)).toList
      }
    }
 
    inversionsInner(collection)
    count
  }
}

aW1wb3J0IGlvLlNvdXJjZQogCm9iamVjdCBNU29ydCB7CiAgZGVmIG1haW4oYXJnczpBcnJheVtTdHJpbmddKSB7CiAgICB2YWwgZmlsZVdpdGhOdW1iZXJzID0gIi9Vc2Vycy90bW9ycm93L0RvY3VtZW50cy9JbnRlZ2VyQXJyYXkudHh0IgogICAgdmFsIGludmVyc2lvbnM6IEJpZ0ludCA9IG51bWJlck9mSW52ZXJzaW9ucyhTb3VyY2UuZnJvbUZpbGUobmV3IGphdmEuaW8uRmlsZShmaWxlV2l0aE51bWJlcnMpKS5nZXRMaW5lcygpLm1hcChJbnRlZ2VyLnBhcnNlSW50KS50b0xpc3QpCiAgICBwcmludGxuKGludmVyc2lvbnMpCiAgfQogCiAgZGVmIG51bWJlck9mSW52ZXJzaW9ucyhjb2xsZWN0aW9uOiBMaXN0W0ludF0pOiBCaWdJbnQgPSB7CiAgICB2YXIgY291bnQ6IEJpZ0ludCA9IDAKICAgIGRlZiBpbnZlcnNpb25zSW5uZXIoaW5uZXJDb2xsZWN0aW9uOiBMaXN0W0ludF0pOiBMaXN0W0ludF0gPSB7CiAgICAgIGRlZiBtZXJnZShsZWZ0OiBMaXN0W0ludF0sIHJpZ2h0OiBMaXN0W0ludF0pOiBTdHJlYW1bSW50XSA9IChsZWZ0LCByaWdodCkgbWF0Y2ggewogICAgICAgIGNhc2UgKHggOjogeHMsIHkgOjogeXMpIGlmIHggPCB5PT4geyBTdHJlYW0uY29ucyh4LCBtZXJnZSh4cywgcmlnaHQpKSB9CiAgICAgICAgY2FzZSAoeCA6OiB4cywgeSA6OiB5cykgPT4geyBjb3VudCA9IGNvdW50ICsgbGVmdC5sZW5ndGg7IFN0cmVhbS5jb25zKHksIG1lcmdlKGxlZnQsIHlzKSkgfQogICAgICAgIGNhc2UgXyA9PiBpZiAobGVmdC5pc0VtcHR5KSByaWdodC50b1N0cmVhbSBlbHNlIGxlZnQudG9TdHJlYW0KICAgICAgfQogICAgICB2YWwgbiA9IGlubmVyQ29sbGVjdGlvbi5sZW5ndGggLyAyCiAgICAgIGlmIChuID09IDApIGlubmVyQ29sbGVjdGlvbgogICAgICBlbHNlIHsKICAgICAgICB2YWwgKGxvd2VySGFsZiwgdXBwZXJIYWxmKSA9IGlubmVyQ29sbGVjdGlvbiBzcGxpdEF0IG4KICAgICAgICBtZXJnZShpbnZlcnNpb25zSW5uZXIobG93ZXJIYWxmKSwgaW52ZXJzaW9uc0lubmVyKHVwcGVySGFsZikpLnRvTGlzdAogICAgICB9CiAgICB9CiAKICAgIGludmVyc2lvbnNJbm5lcihjb2xsZWN0aW9uKQogICAgY291bnQKICB9Cn0=