merge sortの練習

この二ヶ月間ちょい、仕事の方で一杯一杯だったので、全然趣味的なプログラミングができずに、割と悶々としておりました。

で、最近になって落ち着いてきたので、以前少し触っていたScalaを思い出そうとしたら完全に忘れていることに気づきリハビリがてら何か書いてみようかと。あと、EclipseのScala IDEを試したい、など。

object Main {
  def mergeSort[T <% Ordered[T]](xs: List[T]): List[T] = {
    def split(xs: List[T]): (List[T], List[T]) = xs.splitAt(xs.size / 2)

    def merge(ls: List[T], rs: List[T], ms: List[T]): List[T] = (ls, rs) match {
      case (Nil, Nil) => ms
      case (hd :: tl, Nil) => merge(tl, rs, hd :: ms)
      case (Nil, hd :: tl) => merge(ls, tl, hd :: ms)
      case (lhd :: ltl, rhd :: rtl) if lhd < rhd => merge(ltl, rs, lhd :: ms)
      case (lhd :: ltl, rhd :: rtl) => merge(ls, rtl, rhd :: ms)
    }

    def sort(xs: List[T]): List[T] = xs match {
      case Nil => xs
      case x :: Nil => xs
      case _ =>
        val (l, r) = split(xs)
        merge(sort(l), sort(r), Nil).reverse
    }

    sort(xs)
  }

  def main(args: Array[String]): Unit = {
    val sortedInt = mergeSort[Int](List(7, 3, 9, 4, 2, 8, 1, 6, 5))
    println(sortedInt)
    val sortedStr = mergeSort[String](List("qwer", "cvbn", "kjhg", "asdf", "zxcv", "mnbv"))
    println(sortedStr)
  }
}

以前、IntelliJ IDEAを使ってみたときは操作感が気持ち悪い系の印象をもったのですが、EclipseのScala IDEはまぁまともで、動作も軽いのでしばらくこっちを使ってみることにしました。