trait Ord[T] {
  def lt(x: T, y: T): Boolean
}
 
object Ord {
  def sort[T](xs: Seq[T])(implicit ord: Ord[T]): Seq[T] =
    xs match {
      case Seq() => Seq.empty
      case h +: t =>
        val (lesser, greater) = t.partition(ord.lt(_, h))
        sort(lesser) ++ Seq(h) ++ sort(greater)
    }
}
 
object Main extends App {
  implicit val defaultOrd = new Ord[Int] {
    override def lt(x: Int, y: Int) = x < y
  }
 
  val reverseOrd = new Ord[Int] {
    override def lt(x: Int, y: Int) = x > y
  }
 
  println(Ord.sort(Seq(3, 1, 2)))
  println(Ord.sort(Seq(3, 1, 2))(reverseOrd))
}
 

dHJhaXQgT3JkW1RdIHsKICBkZWYgbHQoeDogVCwgeTogVCk6IEJvb2xlYW4KfQoKb2JqZWN0IE9yZCB7CiAgZGVmIHNvcnRbVF0oeHM6IFNlcVtUXSkoaW1wbGljaXQgb3JkOiBPcmRbVF0pOiBTZXFbVF0gPQogICAgeHMgbWF0Y2ggewogICAgICBjYXNlIFNlcSgpID0+IFNlcS5lbXB0eQogICAgICBjYXNlIGggKzogdCA9PgogICAgICAgIHZhbCAobGVzc2VyLCBncmVhdGVyKSA9IHQucGFydGl0aW9uKG9yZC5sdChfLCBoKSkKICAgICAgICBzb3J0KGxlc3NlcikgKysgU2VxKGgpICsrIHNvcnQoZ3JlYXRlcikKICAgIH0KfQoKb2JqZWN0IE1haW4gZXh0ZW5kcyBBcHAgewogIGltcGxpY2l0IHZhbCBkZWZhdWx0T3JkID0gbmV3IE9yZFtJbnRdIHsKICAgIG92ZXJyaWRlIGRlZiBsdCh4OiBJbnQsIHk6IEludCkgPSB4IDwgeQogIH0KCiAgdmFsIHJldmVyc2VPcmQgPSBuZXcgT3JkW0ludF0gewogICAgb3ZlcnJpZGUgZGVmIGx0KHg6IEludCwgeTogSW50KSA9IHggPiB5CiAgfQoKICBwcmludGxuKE9yZC5zb3J0KFNlcSgzLCAxLCAyKSkpCiAgcHJpbnRsbihPcmQuc29ydChTZXEoMywgMSwgMikpKHJldmVyc2VPcmQpKQp9Cg==