Scala : add merge sort to sandbox

2 files changed, 26 insertions, 0 deletions

diff --git a/Scala/sandbox/0-main.scala b/Scala/sandbox/0-main.scala
index 2616f8f..1061f50 100644
--- a/Scala/sandbox/0-main.scala
+++ b/Scala/sandbox/0-main.scala
@@ -12,5 +12,6 @@ object Main  extends App {
     Variance.run
     PatternMatching.run
     Lists.run
+    MergeSort.run
 
 }
diff --git a/Scala/sandbox/10-merge-sort.scala b/Scala/sandbox/10-merge-sort.scala
new file mode 100644
index 0000000..92296e2
--- /dev/null
+++ b/Scala/sandbox/10-merge-sort.scala
@@ -0,0 +1,25 @@
+object MergeSort
+{
+
+  def msort(xs: List[Int]): List[Int] = {
+    val n = xs.length/2
+    if (n==0) xs
+    else {
+      def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match {
+        case (Nil, ys) => ys
+        case (xs, Nil) => xs
+        case (x :: xs1, y :: ys1) => {
+          if (x < y) x :: merge(xs1, ys)
+          else y :: merge(xs, ys1)
+        }
+      }
+      val (fst, snd) = xs splitAt n
+      merge(msort(fst), msort(snd))
+    }
+  }
+
+  def run = {
+    println("MergeSort")
+    println(msort(List(2, 8, -2, 9, 2, 6, 0, 7, 1)))
+  }
+}