Testing MergeSort

SortingSpec.scala

import scala.reflect.classTag
import scala.reflect.ClassTag
import org.scalacheck._
import Sorting._
import Histogram

class Histogram[K](keys: Seq[K]) {
  private val underlying =
    keys.foldLeft(Map.empty[K, Int]) { (m, k) =>
      val count = m.getOrElse(k, 0) + 1
      m + (k -> count)
    }
  
  override def equals(that: Any): Boolean = 
    that match {
      case h: Histogram[K] =>
        h.underlying.equals(underlying)
      case _ => false
    }
  
  override def hashCode: Int = underlying.hashCode
}

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 = {
    val indices = 0 until a.length-1
    val shifted = 1 until a.length
    indices
      .zip(shifted)
      .forall { case (i, j) => o.lteq(a(i), a(j)) }
  }
}

object SortingSpec extends Properties("mergeSort") {
  type Pair = (Int, Int)  // a type alias

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

  val saturated: Gen[Array[Int]] = {
    // One possible way of saturating the array with duplicate keys
    val sized = Gen.sized(s => Gen.choose(0, Math.sqrt(s).toInt))
    Gen.containerOf[Array, Int](sized)
  }

  val pairs: Gen[Array[Pair]] = {
    val n = Gen.choose(0, 5)
    val pair = for {
      i <- n
      j <- n
    } yield (i, j)  // Syntax sugar for n.flatMap(i => n.map(j => (i, j)))
    Gen.containerOf[Array, Pair](pair)
  }

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

  property("keys") = Prop.forAll(unsaturated) { a =>
    val before = new Histogram(a)
    mergeSort(a)
    val after = new Histogram(a)
    before == after
  }

  property("isStable") = Prop.forAll(pairs) { a =>
    val byI = Ordering.by[Pair, Int](_._1)
    val byJ = Ordering.by[Pair, Int](_._2)

    mergeSort(a)(classTag[Pair], byJ)
    mergeSort(a)(classTag[Pair], byI)
    isSorted(a)
  }
}