Merge sort in Scala and Processing (1/3)

(Part 1 2 3)

Someone asked a question about merge sort the other day, and I was inspired to write a Scala implementation of a merge sort routine.

Assuming that we are sorting a list of integers, a recursive solution can be drawn up as follows.

• in case the list has no elements, it is already sorted
  
• in case the list has one element, it is already sorted
  
• otherwise, we can make the list sorted by splitting it in two halves, sort each part, and the merge the parts back together
  

or

  def mergeSort (xs: List[Int]): List[Int] = {
    xs match {
      case Nil     ⇒ xs
      case List(_) ⇒ xs
      case _       ⇒
        val (xs1, xs2) = xs splitAt (xs.size/2)
        merge(mergeSort(xs1), mergeSort(xs2))
    }
  }

In this context, merging two sorted lists means (X_h means the first element, or head, of X, X_t means the rest, or tail, of X):

• in case B is empty, take A
  
• in case A is empty, take B
  
• in case A_h ≤ B_h, take A_h and the result of merging A_t and B
  
• otherwise, take B_h and the result of merging A and B_t
  

or

  def merge (a: List[Int], b: List[Int]): List[Int] =
    (a, b) match {
      case (_, Nil) ⇒ a
      case (Nil, _) ⇒ b
      case (ah :: at, bh :: _) if (ah <= bh) ⇒
        ah :: merge(at, b)
      case (_, bh :: bt) ⇒ bh :: merge(a, bt)
    }

This can be generalized to a sequence of anything that can be ordered:

  def mergeSort[A<%Ordered[A]] (xs:Seq[A]):Seq[A] = {
  def merge (xs1: Seq[A], xs2: Seq[A]): Seq[A] =
    (xs1, xs2) match {
      case (_, Seq()) ⇒ xs1
      case (Seq(), _) ⇒ xs2
      case (Seq(h1, t1 @ _*), Seq(h2, _*))
        if (h1<=h2) ⇒
          Seq(h1) ++ merge(t1, xs2)
      case (_, Seq(h2, t2 @ _*)) ⇒
        Seq(h2) ++ merge(xs1, t2)
  }
  xs match {
    case Seq()  ⇒ xs
    case Seq(_) ⇒ xs
    case _      ⇒
      val (xs1, xs2) = xs splitAt (xs.size/2)
      merge(mergeSort(xs1), mergeSort(xs2))
  }
}

scala> mergeSort("Hello world")
res1: Seq[Char] = List( , H, d, e, l, l, l, o, o, r, w)

Yawn.

Well, that's not very interesting, is it?

Then I thought, how about using Processing to visualize the sorting process?

A Scala/Processing applet could display a sequence of values as a dot-spread diagram, with position on the x-axis and value on the y-axis. It would basically look like this (n is the number of values, s is the pixel size of each dot):

    for (x ← 0 until n) {
      val y = f(x)
      ellipse(x * s, y * s, s-1, s-1)
    }

In Scala, objects and functions are interchangeable, so f acts as a partial function that maps x (for values in the range 0 ≤ x < n) to y values. With this definition, the loop in draw will display n dots on the screen, with a single dot in each column and row.

However, my goal was to show unsorted values getting more and more sorted, in effect an animated view of the sorting process. To do this, I need more than one state. While I'm at it, I'll define a state as an Array of integers, and the state structure as a Sequence (produced by the Seq object):

  val fStates: Seq[Array[Int]] = Seq(
    Array(4, 8, 7, 6, 2, 5, 9, 3, 1, 0),
    Array(4, 8, 7, 2, 6, 5, 9, 3, 0, 1),
    Array(4, 8, 2, 6, 7, 5, 9, 0, 1, 3),
    Array(2, 4, 6, 7, 8, 0, 1, 3, 5, 9),
    Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
  )

  var i = 0

  // ...

    val f = fStates(i)
    for (x ← 0 until f.size) {
      val y = f(x)
      ellipse(x * s, y * s, s-1, s-1)
    }
    i = (i + 1) % fStates.size

This works, but there's room for improvement. For one thing, I don't want to have to specify the values myself, and for another, the indexing exposes too much of the implementation. In the next part, I'll define a factory that produces states and provides them through an iterator, which will let me write the applet this way:

  val numVals = 70
  val dotSize =  6
  val fStates =
    SortStates(Array.range(numVals-1, -1, -1))

  override def setup {
    size(numVals * dotSize, numVals * dotSize)
    frameRate(1)
    smooth
    noStroke
    ellipseMode(CORNER)
  }

  override def draw {
    background(255)
    fill(0)
    val f = fStates.next
    for (x ← 0 until numVals) {
      val y = f(x)
      ellipse(
        x * dotSize,
        y * dotSize,
        dotSize-1,
        dotSize-1
      )
    }
  }

(In this example, the initial state has the values in reverse order.)