Testing MergeSort

SortingSpecification.scala

import scala.reflect.ClassTag
import org.scalacheck._

case class Histogram[K] private (value: Map[K, Int]) {
  def +(key: K): Histogram[K] = {
    val count = value.getOrElse(key, 0) + 1
    Histogram(value + (key -> count))
  }
}

object Histogram {
  def empty[K]: Histogram[K] = new Histogram(Map.empty)

  def apply[K](keys: Seq[K]): Histogram[K] =
    keys.foldLeft(Histogram.empty[K])(_ + _)
}

object Sorting {
  def mergeSort[T: ClassTag](a: Array[T])(implicit o: Ordering[T]): Unit = {
    val aux = new Array[T](a.length) // Use a common auxiliary array

    // Sort the subsequence [l, h]
    def sort(l: Int, h: Int): Unit = {
      if (l < h) {
        val m = l + (h - l) / 2 // Account for integer overflow
        sort(l, m)
        sort(m + 1, h)
        if (o.gt(a(m), a(m + 1))) {
          merge(l, m, h) // Only merge if [l, h] is not in order
        }
      }
    }

    // Merge the sorted subsequences [l, m] and (m, h]
    def merge(l: Int, m: Int, h: Int): Unit = {
      for (i <- l until h + 1) {
        aux(i) = a(i)
      }

      var i = l
      var j = m + 1
      for (k <- l until h + 1) {
        if (i > m) {
          a(k) = aux(j)
          j += 1
        } else if (j > h) {
          a(k) = aux(i)
          i += 1
        } else if (o.lt(aux(j), aux(i))) {
          a(k) = aux(j)
          j += 1
        } else {
          a(k) = aux(i)
          i += 1
        } // n.b. Stable implementation of the algorithm
      }
    }

    sort(0, a.length - 1) // Run the routine on the whole array
  }

  def isSorted[T](a: Array[T])(implicit o: Ordering[T]): Boolean =
    Range(0, a.length - 1).forall(i => o.lteq(a(i), a(i + 1)))
}

object SortingSpecification extends Properties("mergeSort") {
  import Sorting._

  val array: Gen[Array[Int]] =
    Gen.containerOf[Array, Int](Gen.posNum[Int])

  property("isSorted") = Prop.forAll(array) { a =>
    mergeSort(a)
    isSorted(a)
  }

  property("hasSameKeys") = Prop.forAll(array) { a =>
    val before = Histogram(a.toList)
    mergeSort(a)
    val after = Histogram(a.toList)
    before == after
  }
}