ParallelMergeSortLecture.scala

package week2

import java.util.Arrays

import common.ParallelConstructs._

import scala.util.Random
import org.scalameter._

object ParallelMergeSortLecture extends App {
  import java.util.Arrays.{sort => quickSort}

  def merge(src: Array[Int], dst: Array[Int], from: Int, mid: Int, until: Int): Unit = {
    var left = from
    var right = mid
    var merged = from

    while (left < mid && right < until) {
      if (src(left) < src(right)) {
        dst(merged) = src(left)
        left += 1
      } else {
        dst(merged) = src(right)
        right += 1
      }
      merged += 1
    }
    if (left == mid) {
      Array.copy(src, right, dst, merged, (until - right))
    } else {
      Array.copy(src, left, dst, merged, (mid - left))
    }
  }

  def parMergeSort(xs: Array[Int], maxDepth: Int): Unit = {
    val ys = new Array[Int](xs.length)

    def sort(from: Int, until: Int, depth: Int): Unit = {
      if (depth == maxDepth) {
        quickSort(xs, from, until)
      } else {
        val mid = (from + until) / 2

        parallel(sort(from, mid, depth + 1), sort(mid, until, depth + 1))

        val flip = (maxDepth - depth) % 2 == 0
        val (src, dst) = if (flip) (ys, xs) else (xs, ys)

        merge(src, dst, from, mid, until)
      }
    }

    sort(0, xs.length, 0)

    if (maxDepth % 2 == 1) {
      Array.copy(ys, 0, xs, 0, xs.length)
    }
  }

  val random = new Random()
  val xs = Array.fill(10000000){ random.nextInt(1000) }
  val zs = xs.clone()

  val par = withWarmer(new Warmer.Default) measure {
    parMergeSort(xs, 2)
  }

  val seq = withWarmer(new Warmer.Default) measure {
    quickSort(zs)
  }

  assert(Arrays.equals(xs, zs))

  println(s"parallel: $par")
  println(s"sequential: $seq")
  println(s"speedup: ${seq.value / par.value}")
}