sort in functional programming way.md

this gist demonstrates idiomatic way to do sorting of various kinds through functional programming

import scala.math.Ordering
import scala.util.control.TailCalls._

trait Sort {
  def sort[O: Ordering](xs: List[O]): List[O]
  def safeSort[O: Ordering](xs: List[O]): List[O]
}

class InsertionSort extends Sort {
  def sort[O](ls: List[O])(implicit Ord: Ordering[O]): List[O] = {
    def insert(x: O, xs: List[O]): List[O] =
      xs match {
        case Nil => List(x)
        case y :: ys =>
          if (Ord.compare(x, y) < 0) x :: y :: ys
          else y :: insert(x, ys)
      }

    ls match {
      case Nil => Nil
      case x :: xs => insert(x, sort(xs))
    }
  }

  private def isort[O](ls: List[O])(implicit Ord: Ordering[O]): TailRec[List[O]] = {
    def insert(x: O, xs: List[O]): TailRec[List[O]] =
      xs match {
        case Nil => done(List(x))
        case y :: ys =>
          if (Ord.compare(x, y) < 0) done(x :: y :: ys)
          else insert(x, ys).map(y :: _)
      }

    ls match {
      case Nil => done(Nil)
      case x :: xs =>
        isort(xs).flatMap(insert(x, _))
    }
  }

  override def safeSort[O: Ordering](xs: List[O]): List[O] = isort(xs).result
}

class SelectionSort extends Sort {
  def sort[O](ls: List[O])(implicit Ord: Ordering[O]): List[O] = {
    def select(xs: List[O]): (O, List[O]) =
      xs match {
        case Nil => throw new RuntimeException("not possible")
        case x :: Nil => (x, Nil)
        case y :: ys =>
          val (z, zs) = select(ys)
          if (Ord.compare(y, z) < 0) (y, z :: zs)
          else (z, y :: zs)
      }

    ls match {
      case Nil => Nil
      case _ =>
        val (x, xs) = select(ls)
        x :: sort(xs)
    }
  }

  private def isort[O](ls: List[O])(implicit Ord: Ordering[O]): TailRec[List[O]] = {
    def select(xs: List[O]): TailRec[(O, List[O])] =
      xs match {
        case Nil => throw new RuntimeException("not possible")
        case x :: Nil => done((x, Nil))
        case y :: ys =>
          select(ys) map { case (z, zs) =>
            if (Ord.compare(y, z) < 0) (y, z :: zs)
            else (z, y :: zs)
          }
      }

    ls match {
      case Nil => done(Nil)
      case _ =>
        select(ls).flatMap { case (x, xs) =>
          isort(xs).map(x :: _)
        }
    }
  }

  override def safeSort[O: Ordering](xs: List[O]): List[O] = isort(xs).result
}