Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Testing MergeSort
import scala.reflect.ClassTag
import org.scalacheck._
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 =
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("keys") = Prop.forAll(array) { a =>
val before = new Histogram(a)
mergeSort(a)
val after = new Histogram(a)
before == after
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment