Skip to content

Instantly share code, notes, and snippets.

@fancellu
Created November 25, 2015 12:12
  • Star 7 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save fancellu/5e00336840098c194551 to your computer and use it in GitHub Desktop.
MergeSort in Scala with recursive merge
object MergeSort {
// recursive merge of 2 sorted lists
def merge(left: List[Int], right: List[Int]): List[Int] =
(left, right) match {
case(left, Nil) => left
case(Nil, right) => right
case(leftHead :: leftTail, rightHead :: rightTail) =>
if (leftHead < rightHead) leftHead::merge(leftTail, right)
else rightHead :: merge(left, rightTail)
}
def mergeSort(list: List[Int]): List[Int] = {
val n = list.length / 2
if (n == 0) list // i.e. if list is empty or single value, no sorting needed
else {
val (left, right) = list.splitAt(n)
merge(mergeSort(left), mergeSort(right))
}
}
mergeSort(List(33,44,22,-10,99)) //> res0: List[Int] = List(-10, 22, 33, 44, 99)
mergeSort(List()) //> res1: List[Int] = List()
}
@antonallote
Copy link

Also the MergeSort function can be defined with pattern matching:

def mergeSort(list: List[Int]): List[Int] = list match {
case Nil => Nil
case xs::Nil => List(xs)
case _ =>
val (left, right) = list splitAt list.length/2
merge(mergeSort(left), mergeSort(right))
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment