Sorting

gistfile1.scala

object MySorts extends Ordering.ExtraImplicits {

  def mergeSort[T : Ordering](elems: List[T]): List[T] = elems match {
    case Nil | _::Nil => elems
    case that =>
      type L = List[T]
      def merge(l1: L, l2: L, acc: L): L = l1 -> l2 match {
        case (a::as, b::_) if a < b => merge(as, l2, a::acc)
        case (_, b::bs) =>  merge(l1, bs, b::acc)
        case (a::as, _) =>  merge(as, l2, a::acc)
        case _ => acc.reverse
      }
      val (bot, top) = elems.splitAt(elems.length / 2)
      val bs = mergeSort(bot)
      val ts = mergeSort(top)
      merge(bs, ts, Nil)
  }

  def qsort[T : Ordering](seq: List[T]): List[T] = seq match {
    case Nil => Nil
    case pivot::tail =>
      val (lt, gt) = tail.partition(pivot >)
      qsort(lt) ++ (pivot::Nil) ++ qsort(gt)
  }
}