Odds and Ends
In the first two parts, I demonstrated visualization of the process of merge sorting an array of integers. In this part I will describe the two steps left undescribed: how to create a collection of stages and how to create a repeating iterator. I will also present a shuffling function that can be used to create the initial state.
The Stages class
The Stages class provides a map method which is used by the SortStates class to create a collection of states. The function that creates one of the states needs to 1) see the state array (which contains the previous state) and 2) be told how to rearrange it into the next state. The actual function passed to map is curried with the state array, so the only thing map needs to prepare is the collection of stages of rearrangement information.
class Stages (n: Int) {
Define generate method
def map (f: List[Int] => Array[Int]) =
generate() map f
}
Define generate method
The generate method creates the stages recursively, bottoming out when the parameter i exceeds n.
private def generate (i: Int = 2): List[List[Int]] = {
Define split subroutine
if (n <= i) {
Base case
} else {
Preceding cases
}
}
Base case
In the base case, the state array (whose length is stored in the n field) is in a partially sorted state where two sublists of roughly equal length are individually sorted (e.g. Array(1, 3, 5, 0, 2, 4)) and are to be merged into a completely sorted array. The conversion function, of class StateFunc (described in part 2), will be able perform this operation if given a list containing the total length of the sublists, i.e. List(n).
List(n) :: Nil
Preceding cases
In each of the cases preceding the base case, the state array consists of k pairs of sorted sublists that are to be merged into k sorted sublists (which will be merged in the next stage, and so on). Thus, in the general case Cx the stage information is a list of 2 × k integers where the sum of each pair is equal to the corresponding integer in the stage information of the following case Cx+1.
val tail = generate(2 * i)
split(tail.head) :: tail
Define split subroutine
The split subroutine uses h to create a list of integers whose size is twice that of h and where every element e ∈ h is mapped to two elements, the first being e/2 and the second being e-e/2.
def split (h: List[Int]) =
h flatMap { e => List(e/2, e-e/2) }
The RepeatingIterator class
The RepeatingIterator class trivially encapsulates a sequence and overrides the next method to reset the internal iterator every time it is exhausted. The hasNext method accordingly always returns true.
class RepeatingIterator[A] (xs: Seq[A]) extends Iterator[A] {
private var iter = xs.iterator
override def hasNext = true
override def next () = {
if (!iter.hasNext) iter = xs.iterator
iter.next
}
}
Shuffling the values
In the example, I passed an array of values in reverse order to SortStates. Alternatively, the array can be shuffled like this:
object Shuffle {
private val rand = new scala.util.Random
def apply[A] (xs: Array[A]) = {
for (n <- 0 until xs.size) {
val k = n + rand.nextInt(xs.size-n)
val v = xs(k)
xs(k) = xs(n)
xs(n) = v
}
xs take xs.size
}
}
And that's merge sort.
