Scala Solutions for Week 1 of Coursera/Stanford Algorithms: Design and Analysis, Part 1

I am currently taking Stanford's Algorithms: Design and Analysis, Part 1 class on Coursera.

I wanted to share my solutions which I am writing in Scala.

Count Inversions using Merge Sort

package algo

import scala.math  
import Ordering.Implicits._  
import Numeric.Implicits._

object CountInversions {

  private[this] def inversions[T : Numeric](arr: Array[T], low: Int, high: Int, count: Long, sorted: Array[T])(implicit c: scala.reflect.ClassTag[T]): (Long, Array[T]) = {
    val diff = (high - low) + 1
    val med = (high + low) / 2
    diff match {
      case x if x <= 1 =>
        (0, Array[T](arr(low)))

      case 2 =>
        val i1 = arr(low)
        val i2 = arr(high)
        if (i1 > i2) (1, Array(i2, i1))
        else (0, Array(i1, i2))

      case _ =>
        val (leftCount, leftArray) = inversions(arr, low, med, count, sorted)
        val (rightCount, rightArray) = inversions(arr, med + 1, high, count, sorted)

        merge(leftArray, rightArray, leftCount + rightCount, sorted)
    }
  }

  @scala.annotation.tailrec
  private[this] def merge[T : Numeric](l: Array[T], r: Array[T], count: Long, sorted: Array[T])(implicit c: scala.reflect.ClassTag[T]): (Long, Array[T]) = {
    (l, r) match {
      case (Array(), _) =>
        (count, sorted ++ r)

      case (_, Array()) =>
        (count, sorted ++ l)

      case _ =>
        val l1 = l.head
        val r1 = r.head
        val ls = l slice (1, l.size)
        val rs = r slice (1, r.size)

        (l1 <= r1) match {
          case true =>
            merge(ls, r, count, sorted ++ Array[T](l1))

          case false =>
            merge(l, rs, l.size + count, sorted ++ Array[T](r1))
        }
    }
  }

  def apply[T : Numeric](arr: Array[T])(implicit c: scala.reflect.ClassTag[T]): (Long, List[T]) = {
    val (count, items) = inversions[T](arr, 0, arr.length - 1, 0l, Array[T]())
    (count, items.toList)
  }

}

The test cases can be found here.

Merge Sort

package algo

import scala.math  
import Ordering.Implicits._  
import Numeric.Implicits._

object MergeSort {

  private[this] def mergeSort[T : Numeric](arr: Array[T])(implicit c: scala.reflect.ClassTag[T]): Array[T] = {
    arr.size match {
      case x if x <= 1 =>
        arr

      case 2 =>
        Array[T](arr.min, arr.max)

      case _ =>
        val med = arr.size / 2
        val l = mergeSort(arr.slice(0, med))
        val r = mergeSort(arr.slice(med, arr.size))

        merge(l, r)
    }
  }

  private[this] def merge[T : Numeric](l: Array[T], r: Array[T])(implicit c: scala.reflect.ClassTag[T]): Array[T] = {
    (l, r) match {
      case (Array(), _) => r
      case (_, Array()) => l
      case _ =>
        val l1 = l.head
        val r1 = r.head
        val ls = l slice (1, l.size)
        val rs = r slice (1, r.size)

        if (l1 < r1)  Array[T](l1) ++ merge(ls, r)
        else Array[T](r1) ++ merge(l, rs)
    }
  }

  def apply[T : Numeric](arr: Array[T])(implicit c: scala.reflect.ClassTag[T]): Array[T] = {
    mergeSort[T](arr)
  }

  def test[T : Numeric](arr: Array[T])(implicit c: scala.reflect.ClassTag[T]): Unit = {
    val expected = arr.sorted.toList
    val output = apply(arr).toList
    (output == expected) match {
      case true => println(s"OK: ${arr.toList}")
      case false => println(s"FAILED - Input: ${arr.toList}, Output: $output, Expected: $expected")
    }
  }

  def main(args: Array[String]): Unit = {
    List(
      Array(1, 4, 50, 20, 10)
    ) foreach test[Int]
  }

}