From 72c432e120c4bc4651f2f00c8e34653d446128ae Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Thu, 9 May 2013 21:12:26 +0200
Subject: Scala : add merge sort to sandbox

---
 Scala/sandbox/0-main.scala        |  1 +
 Scala/sandbox/10-merge-sort.scala | 25 +++++++++++++++++++++++++
 2 files changed, 26 insertions(+)
 create mode 100644 Scala/sandbox/10-merge-sort.scala

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)))
+  }
+}
-- 
cgit v1.1-2-g2b99