mergeSort.scala

package com.mehalter

import scala.util.Random

import scalaz.stream._
import scalaz.concurrent.Task

object mergeSort {
    def main(args: Array[String]): Unit = {
        val a: List[Int] = Random.shuffle((1 to 100).toList)
        val merged = mergeSort(a)

        println(merged)
    }

    def mergeSort(list: List[Int]): List[Int] = {

        if (list.length == 1) return list

        var l1 = list.drop(list.length/2)
        var l2 = list.dropRight(list.length - (list.length/2))

        val sorted = mergeSort(l1)
        val sorted2 = mergeSort(l2)

        merge(sorted, sorted2)
    }

    def merge(l1: List[Int], l2: List[Int]): List[Int] = {
        val p1 = Process(l1: _*)
        val p2 = Process(l2: _*)

        def next(l: Int, r: Int): Tee[Int, Int, Int] = if (implicitly[Ordering[Int]].lt(l, r))
            Process.emit(l) ++ nextL(r)
        else
            Process.emit(r) ++ nextR(l)

        def nextR(l: Int): Tee[Int, Int, Int] =
            tee.receiveROr[Int, Int, Int](Process.emit(l) ++ tee.passL)(next(l, _))
        def nextL(r: Int): Tee[Int, Int, Int] =
            tee.receiveLOr[Int, Int, Int](Process.emit(r) ++ tee.passR)(next(_, r))

        def sortedMergeStart: Tee[Int, Int, Int] =
            tee.receiveLOr[Int, Int, Int](tee.passR)(nextR)

        p2.tee(p1)(sortedMergeStart).toSource.runLog.run.toList
    }
}