Algo class assignment 1

assignment1.scala

val numbers = io.Source.fromFile("IntegerArray.txt").getLines.map({v => v.toInt}).toArray

def analyze(a : Array[Int]) : Tuple2[Long, Array[Int]] = a.size match {
	case 1 => (0, a.clone)
	case 2 => if (a(0) > a(1)) (1, a.reverse) else (0, a)
	case _ => {
		val l = a.size / 2
		val (lcount, larr) = analyze(a.slice(0, l).toArray)
		val (rcount, rarr) = analyze(a.slice(l, a.size).toArray)

		// merge & count inversions
		val invs = merge(a, larr, rarr) + lcount + rcount
		return (invs, a)
	}
}

def merge(dest : Array[Int], left: Array[Int], right: Array[Int]) : Long = {
	var li = 0
	var ri = 0
	var invs = 0L
	for(i <- 0 until dest.size) {
		if (li < left.size && (ri >= right.size || left(li) < right(ri) ) ) {
			dest(i) = left(li)
			li = li + 1
		}
		else if (ri < right.size) {
			invs += (left.size - li)

			dest(i) = right(ri)
			ri = ri + 1
		}
	}
	return invs
}

val (inversions, _) = analyze(numbers)

println(inversions)