Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Sorting
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)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.