Parallel Merge Sort in Scala

Question

I have been trying to implement parallel merge sort in Scala. My current implementation is about as fast as .sorted, but I have no idea what would be the right aproach to parallelize it.

Input file with 1.2M integers:

• 1.333580 seconds (my implementation)
• 1.439293 seconds (.sorted)

How should I parallelize this?

object Mergesort extends App { //===================================================================================================================== // UTILITY implicit object comp extends Ordering[Any] { def compare(a: Any, b: Any) = { (a, b) match { case (a: Int, b: Int) => a compare b case (a: String, b: String) => a compare b case _ => 0 } } } //===================================================================================================================== // MERGESORT val THRESHOLD = 30 def inssort[A](a: Array[A], left: Int, right: Int): Array[A] = { for (i <- (left+1) until right) { var j = i val item = a(j) while (j > left && comp.lt(item,a(j-1))) { a(j) = a(j-1) j -= 1 } a(j) = item } a } def mergesort_merge[A](a: Array[A], temp: Array[A], left: Int, right: Int, mid: Int) : Array[A] = { var i = left var j = right while (i < mid) { temp(i) = a(i); i+=1; } while (j > mid) { temp(i) = a(j-1); i+=1; j-=1; } i = left j = right-1 var k = left while (k < right) { if (comp.lt(temp(i), temp(j))) { a(k) = temp(i); i+=1; k+=1; } else { a(k) = temp(j); j-=1; k+=1; } } a } def mergesort_split[A](a: Array[A], temp: Array[A], left: Int, right: Int): Array[A] = { if (right-left == 1) a if ((right-left) > THRESHOLD) { val mid = (left+right)/2 mergesort_split(a, temp, left, mid) mergesort_split(a, temp, mid, right) mergesort_merge(a, temp, left, right, mid) } else inssort(a, left, right) } def mergesort[A: ClassTag](a: Array[A]): Array[A] = { val temp = new Array[A](a.size) mergesort_split(a, temp, 0, a.size) } }